2
$\begingroup$

I am aware that the question is asked before but i there is still a confusing part for me.

In book the solution is like that:

  1. $T(n) = 2T(\sqrt{n}) + \log(n)$

  2. $m = \log n$ yields

  3. $T(2^m) = 2T(2^{m/2}) + m$

  4. Then $S(m) = T(2^m)$ produces the recurrence:

  5. $S(m) = 2S(m/2) + m$

  6. So $T(n) = T(2^m) = S(m) = O(m\log m) = O(\log n (\log {\log n}))$

But i can't understand in part $5$, how $2T(2^{m/2})$ is converted to $2S(2m/2)$ ? If $S(m)$ is $T(2^m)$, then $S(m/2)$ must be $T(2^{m-1})$? Can you verify me that why the book's solution is correct, and i am wrong?

$\endgroup$
1
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$
    – Raphael
    Oct 8, 2017 at 16:51

1 Answer 1

4
$\begingroup$

We define $S(m)$ to be $T(2^m)$, for every possible value of $m$. Changing the name of the variable, $S(M) = T(2^M)$ for every value of $M$. Substituting $M := m/2$, we get $S(m/2) = T(2^{m/2})$.

As an example, suppose that $T$ is the identity function: $T(n) = n$. We define $S(m) = T(2^m) = 2^m$. Then $S(m/2) = 2^{m/2}$.

$\endgroup$

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.