I'm trying to solve the recurrence equation from CLRS ed 2. $$ T(n) = 2T(\sqrt{n}) + 1 $$ The question says the solution should be asymptotically tight, but at first I didn't read it and solved it with a substitution of variables and tried to find a big-O solution. $$ m = lg(n) \\ S(m) = T(2^m) \\ S(m) = 2S(m/2)+1 $$ After this, I guessed the solution to be O(lgn) and proved it; changing back the m's to be in the form of n I got T(n) to be O(lglgn).

However, this is not a tight bound and after changing my guess for S(m) from O(lgm) to Θ(m) it worked. The resulting analysis led me to T(n) being Θ(lgn).

Though this is the part that confuses me, how can a function be O(lglgn) yet Θ(lgn)? I can't seem to find my error.

  • $\begingroup$ You made a mistake when you found that $S(m)$ is $O(\log m)$. Try using the master theorem for example and see what this gives you. $\endgroup$
    – Tassle
    Commented Jul 4, 2022 at 8:03

1 Answer 1


Set $n=2^{2^m}$. The recurrence turns to




This is an ordinary linear recurrence. By inspection it has the particular solution $S_p(m)=-1$, and the homogeneous part of the equation is solved by


From this,

$$T(n)=S(m)=C\,2^m-1=C\,\log n-1.$$


$$C\,\log n-1=2(C\log\sqrt n-1)+1=\frac22C\,\log n-2+1.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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