From 591ebd0e965a7849d53e5a2543c814db6468321b Mon Sep 17 00:00:00 2001
From: JBatzill <batzilljohannes@gmail.com>
Date: Wed, 2 Dec 2015 22:37:54 +0100
Subject: added runtime of rmq

---
 datastructures/RMQ.cpp | 2 ++
 1 file changed, 2 insertions(+)

(limited to 'datastructures')

diff --git a/datastructures/RMQ.cpp b/datastructures/RMQ.cpp
index 9047b33..3c3f44c 100644
--- a/datastructures/RMQ.cpp
+++ b/datastructures/RMQ.cpp
@@ -1,6 +1,7 @@
 vector<int> data(RMQ_SIZE);
 vector<vector<int>> rmq(floor(log2(RMQ_SIZE)) + 1, vector<int>(RMQ_SIZE));
 
+//Runtime: O(n*log(n))
 void initRMQ() {
 	for(int i = 0, s = 1, ss = 1; s <= RMQ_SIZE; ss=s, s*=2, i++) {
 		for(int l = 0; l + s <= RMQ_SIZE; l++) {
@@ -13,6 +14,7 @@ void initRMQ() {
 	}
 }
 //returns index of minimum! [l, r)
+//Runtime: O(1)
 int queryRMQ(int l, int r) {
 	if(l >= r) return l;
 	int s = floor(log2(r-l)); r = r - (1 << s);
-- 
cgit v1.2.3