# Why is this $O(\log \log n)$?

Why is this $O(\log \log n)$?

// Here c is a constant greater than 1
for (int i = 2; i <=n; i = pow(i, c)) {
// some O(1) expressions
}

I am trying to understand how I would derive the time complexity of something like this.

• Please write your questions in a way that knwoledge of the syntax of some unspecified language is not needed. What does pow(i,c) mean $i^c$ or $c^i$ or something else. – quid Jan 23 '16 at 21:36
• Because if $N=2^{c^n}$ then $n=\log_c\log_2N$ hence $n=O(\log\log N)$. – Did Jan 23 '16 at 21:37
• @Did I think my problem was seeing what $N$ needed to be stated as $(N = 2^{c^n})$, thanks – Nakano Jan 23 '16 at 21:48

Note that on the $k$th iteration we have $$i=2^{c^k}$$ The loop ends if $i>n$, meaning $$2^{c^k}>n$$ $$c^k>\log_2 n$$ $$k\log_2 c>\log_2\log_2 n$$ $$k>\log_2\log_2 n/\log_2 c$$ Thus there are fewer than a constant multiple of $\log_2\log_2 n$ iterations.
• I think third line should be $k \log c > \log \log_2 n$ which leads to $k > \log_c \log_2 n$, perhaps? – Nakano Jan 23 '16 at 21:47
• What I mean is on the third line you apply $\log$ to the left side but $\log_2$ to the right – Nakano Jan 23 '16 at 21:49