What's the time complexity of the following code?

Question

What's the time complexity of the following code?

a = 2;
while (a <= n)
{
  for (k=1; k <= n; k++)
  {
    b = n;
    while (b > 1)
      b = b / 2;
  }
  a = a * a * a;
}

I'm struggling with the outer while loop, which is loglogn, I can't understand why. How would the time complexity change if the last line was a = a * a * a * a;?

the for loop is O(n), and inner one is O(logn).

So in total, O(n*logn*loglogn)

Yar Yar · Accepted Answer · 2016-09-10T18:36:51

a values would be: a = 2 2^3 2^9 2^27 2^81 ... and so on.

Now let's assume that the last value of a is 2^(3^k)

Where k is the number of iterations of the outer while loop.

For simplicity let's assume that a = n^3, so 2^(3^k) = n^3

So 3^k = 3*log_2(n) => k = log_3(3log_2(n)) = 𝛩(loglogn)

If the last line was a = a * a * a * a the time-complexity would remain 𝛩(loglogn) because k = log_4(4log_2(n)) = 𝛩(loglogn).

What's the time complexity of the following code?

2 Answers