How do you work out the time complexity of this?
int count=0;
for (int i=1 ; i < n; i*=4)
for (int j=1;j<=n;j++)
count++;
-
1At least take the time to format your couple of lines of code. Also, you asked for help but didn't really explain where exactly you are stuck. You've basically just given us a homework assignment.Charles McKelvey– Charles McKelvey2016-08-22 17:23:13 +00:00Commented Aug 22, 2016 at 17:23
-
Just trying to find out how to get T(n) from the code snippets. Would t(n) = O( n^2 ) or would it be O(log (n)). Its not homework. its a question from a past test. and just really having a problem understanding itWWBM– WWBM2016-08-22 17:29:17 +00:00Commented Aug 22, 2016 at 17:29
-
Why do you think it would be either one of those? Again, you should explain the way you understand it and be very specific about which part you are confused with.Charles McKelvey– Charles McKelvey2016-08-22 17:30:51 +00:00Commented Aug 22, 2016 at 17:30
-
They way it was in my textbook was, n from the first loop * n from the second loop = n^2. But ive seen in done in a long method resulting in o(log(n)). So wasnt sure which way was correct. Thats what confused meWWBM– WWBM2016-08-22 17:33:44 +00:00Commented Aug 22, 2016 at 17:33
Add a comment
|
1 Answer
tl;dr: Complexity of the posted code is: O(nlogn)
Let's analyze it from the inside out. The inner loop repeats itself exactly n times for each value of i.
The outer loop repeats itself while i < n, and i is multiplies by 4 each time. This means, after the first iteration, i=1, then i=4, i=16, i=64, .... and after the k'th iteration i = 4^(k-1).
This means, you stop when:
i >= n
4^(k-1) >= n
log_4(4^(k-1)) >= log_4(n)
k-1 >= log_4(n).
This means the outer loop will repeat log_4(n) + 1.
Summing it all together gives you n*(log_4(n)+1) times the inner loop repeats, which is in O(nlogn)
