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

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

1 Answer 1

Reset to default
1
$\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})$.

Improve this answer
$\endgroup$
3
  • $\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, 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$
    – Yuval Filmus
    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$
    – Yuval Filmus
    May 25, 2020 at 11:51

Your Answer

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

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