CODEWITHSUNDEEP
time-complexitybig-ocomplexity-theory
Mosko
Mosko

Reputation: 57

How do I properly calculate this time complexity

I'm examining this code as preparation for my test and I'm having some problems figuring out what is the correct time complexity:

a = 1;
while (a < n) {
 b = 1;
 while (b < a^2)
  b++;
a = a*2;
}

The values for a are as follows : 1, 2, 4, 8, ... , 2^(logn) = n

Therefore we have logn iterations for the outer loop. In every nested loop, there are a^2 iterations, so basically what I've come up with is:

T(n) = 1 + 4 + 16 + 64 + ... + (2^logn)^2

I'm having problems finding the general term of this series and therefore getting to a final result. (maybe due to being completely off in my calculations though)

Would appreciate any help, thank you.

Upvotes: 0

Views: 49

Answers (1)

0Interest
0Interest

Reputation: 1842

Your calculations are alright, you are correct with your analysis of the inner while-loop. We can demonstrate this with a small table:

enter image description here

This is basically the sum of a geometric progression with:
a1 = 1, q = 4, #n = lg n + 1

Where #n is the number of elements.
We have: Sn = 1 * (4^(lgn +1) - 1)/(4-3) = (4*n^2 - 1)/3

Thus we can say your code running complexity is Θ(n^2)

Mathematical explanation in LaTeX:

enter image description here

Upvotes: 1

Related Questions