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.

  • $\begingroup$ 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. $\endgroup$ – quid Jan 23 '16 at 21:36
  • 1
    $\begingroup$ Because if $N=2^{c^n}$ then $n=\log_c\log_2N$ hence $n=O(\log\log N)$. $\endgroup$ – Did Jan 23 '16 at 21:37
  • $\begingroup$ @Did I think my problem was seeing what $N$ needed to be stated as $(N = 2^{c^n})$, thanks $\endgroup$ – 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.

  • $\begingroup$ I think third line should be $k \log c > \log \log_2 n$ which leads to $k > \log_c \log_2 n$, perhaps? $\endgroup$ – Nakano Jan 23 '16 at 21:47
  • $\begingroup$ What I mean is on the third line you apply $\log$ to the left side but $\log_2$ to the right $\endgroup$ – Nakano Jan 23 '16 at 21:49
  • $\begingroup$ Oh that was a typo. I'll fix it. $\endgroup$ – Matt Samuel Jan 23 '16 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.