# Proving van Emde Boas recurrence

I have tried to solve the following question:

van Emde Boas Bounds Show that $$T(u) = T(\sqrt{u}) + O(1)$$ has the solution $$T(u) = O(\log\log u)$$. Hint: consider the binary representation of $$u$$.

In CLRS (Introduction to Algorithms), they make use of the master method case 2. They let $$m = \log_2u$$ so we have $$T(2^m) = T(2^{m/2}) +O(1)$$. Then they substitute $$T(2^m) = S(m)$$ and the recurrence looks as follows:

$$S(m) = S(m/2) + O(1).$$

The above confuses me, because I don't see how $$S(m/2)$$ is the same as $$T(2^{m/2})$$. Taking half of $$m$$ is not the same as taking half of the exponent $$m$$.

• If $S(m) = T(2^m)$ for all $m$, then $S(m/2) = T(2^{m/2})$. – Yuval Filmus May 25 '20 at 11:28
• it does not make sense, if you take half om m (i.e. $m/2$) you don't get the same as $2^{m/2}$. Fx: $2^{log_216/2} = 4$ but $log_216/2 = 8$. – GoldenRetriever May 25 '20 at 12:01
• You can try it out in python. Let's say that $S(m) = 2^m$, i.e. def S(m): return 2**m. Then $S(8) = 256 = 2^8$ and $S(8/2) = 16 = 2^{8/2}$. Try it out! – Yuval Filmus May 25 '20 at 12:07