Search code examples
time-complexitybig-ocomplexity-theory

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.

Solution

  • 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