Time complexity for this simple loop

Question

This is the code:

j=2
while j<(n*n)
     j=j*j

---

At first my approach was to treat this like this loop

i=1
while (i<n)
    i=i*2

Which generates on $i$ various powers of $2$ ($i=2^0, 2^1, 2^2....2^k$).

At a certain $k$ iteration, $i$ is equal to or exceeds $n$. So $2^k=n$ is the time when the while stops.

We find $k=log_2(n)$ which is the number of times the entire while loop has been executed, so $T(n)=\theta(log_2n)$.

---

So my idea for the first algorithm was this: j=j*j generates on $j$ different powers of himself, so you can describe it as $j^2$. The problem is that I can't shove in a $k$ iterations in the counting.

The solution for this is actually $log(log(n))$.

Why is this? Can I improve my logic?

Answer 1

Iterating i=2*i generates the powers of two, as you mentioned.

$$ 2=2^1 \quad 2*2^1=2^2 \quad 2*2^2 = 2^3 \quad 2*3^2 = 2^4 \quad \ldots $$

Iterating j=j*j instead does something more aggressive:

$$ 2 = 2^1 \quad 2^1*2^1=2^2 \quad 2^2*2^2=2^4 \quad 2^4*2^4=2^8 \quad\ldots $$

Note how the exponents grow. In the i sequence they are $1,2,3,4,\ldots$. But in the j sequence they are $1,2,4,8,\ldots$. That is, the exponents themselves grow exponentially!

So, the $k$-th element in the first sequence is $2^k$ while in the second it is $2^{2^k}$. That's why the first loop has complexity $O(\log_2 n)$ and the second one $O(\log_2 (log_2 n))$.

Answer 2

You're on the right track. For the simpler code, you correctly wrote down the sequence of values that are produced: $2^0,2^1,2^2,\dots$. In particular, the $t$th output is $2^t$. Then you were able to find where the loop stops by setting $2^t=n$ and solving for $t$. That's a great approach.

Try doing the same thing for your actual example. Hint: the first two outputs are $j$ and $j^2$. What's next? Can you generalize What is the $t$th output? Can you write an equation that represents where the loop stops and solve for $t$?