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$.

  • $\begingroup$ If $S(m) = T(2^m)$ for all $m$, then $S(m/2) = T(2^{m/2})$. $\endgroup$ May 25, 2020 at 11:28
  • $\begingroup$ 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$. $\endgroup$ May 25, 2020 at 12:01
  • $\begingroup$ 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! $\endgroup$ May 25, 2020 at 12:07
  • $\begingroup$ @GoldenRetriever: I believe you're interpreting $log_2 16 / 2$ inconsistently. $(log_2 16) / 2 \not= log_2 (16 / 2$)$. $\endgroup$ Jun 24, 2020 at 13:58

1 Answer 1


The idea is to define a new function $S(m)$ by $S(m) = T(2^m)$. Then by definition we have $S(m/2) = T(2^{m/2}) = T(\sqrt{2^m})$.

  • $\begingroup$ So we are allowed to say that $S(m/2) = T(2^{m/2})$ even though, algebraically, it's not the same? But why is that the case? How can we make a proof on something we invent? $\endgroup$ May 25, 2020 at 11:46
  • $\begingroup$ In fact, algebraically it is the case. By definition, $S(a) = T(2^a)$. That's how we define $S$. You can substitute anything for $a$, using the principle of substitution of equals-by-equals. $\endgroup$ May 25, 2020 at 11:50
  • 1
    $\begingroup$ You ask why we are allowed to invent things. The master theorem states that if a function $f$ satisfies condition such-and-such, then it has so-and-so asymptotics. It applies to any function, for example to the function $S$ given by the formula $S(m) = T(2^m)$. $\endgroup$ May 25, 2020 at 11:51

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.