Prove a tight bound on the runtime of the following algoirthm

Question

function myfunc(n):
    // n is a positive integer greater than or equal to 2
    i = 2;
    while (i <= n):
        i = i * i
    return;

We know that if we have $i = i * 2$ in the loop body, the runtime would be $log_2(n)$. What would be the runtime if we have $i = i * i$ in the body?

Answer 1

When the loop body is i = i * 2, we see that i grows like this: $$ 2^1, 2^2, 2^3, 2^4, 2^5, \ldots $$ The general term is $a_k = 2^k$, and by taking the inverse function we see that the runtime is $O(\log_2 n)$.

---

Likewise, when the loop body is i = i * i, we see that i grows like this: $$ 2^1, 2^2, 2^4, 2^8, 2^{16}, \ldots $$ The general term is $b_k = 2^{2^{k-1}}$, and by taking the inverse function we see that the runtime is $O(\log_2 \log_2 n)$.