1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ If $S(m) = T(2^m)$ for all $m$, then $S(m/2) = T(2^{m/2})$. $\endgroup$ – Yuval Filmus May 25 '20 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$ – GoldenRetriever May 25 '20 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$ – Yuval Filmus May 25 '20 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$ – reinierpost Jun 24 '20 at 13:58
0
$\begingroup$

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

$\endgroup$
  • $\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$ – GoldenRetriever May 25 '20 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$ – Yuval Filmus May 25 '20 at 11:50
  • $\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$ – Yuval Filmus May 25 '20 at 11:51

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.