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?

  • $\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 '17 at 16:51

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


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.