0
$\begingroup$

This question has already been asked before in this site, but the details of none of them is my question and none of them answer my question. The following is an example recurrence given in introduction to algorithms book by CLRS .

$$T(n) = 2T(\sqrt n) + \log n$$

It is solved by changing the variables. It renames the $m = \log n$ and it yields

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

and it renames $S(m) = T(2^m)$, so it produces new recurrence

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

which is easy to solve.

I have two problems with this solution:

1- renaming $S(m) = T(2^m)$ must yield $S(m) = S(m/2) + \log m$, since we can't change the argument of the $T$ and leave the $m$ as it was. We can use $S(m) = S(m/2) + m$ only if the original recurrence was $T(2^m) = 2T(2^{m/2}) + 2^m$

2- The second problem is, even if the above renaming is true, $2T(\dfrac{2^m}{2})$ would be $S(m/2)$ not the $2T(2^{m/2})$

thanks in advance.

$\endgroup$
4
  • $\begingroup$ What is your question? What specifically don't you like about other answers? $\endgroup$ – Raphael Oct 21 '17 at 16:18
  • $\begingroup$ Another duplicate. $\endgroup$ – Raphael Oct 21 '17 at 16:18
  • $\begingroup$ @Raphael I already read that answer. I want to know why the renaming of functions doesn't change the $m$ to $2^m$ $\endgroup$ – M a m a D Oct 21 '17 at 16:21
  • $\begingroup$ I guess it's unclear why you'd think it should. You already went from $\log n$ to $m$; that's where the substitution happened. The definition of $S$ does not change anything more. $\endgroup$ – Raphael Oct 21 '17 at 16:24
1
$\begingroup$

Regarding your 1st problem: You don't need to change $m$ to $\log m$. Let's suppose $f(x)=g(y)$.Then you do not need substitute $y$ anywhere. Because $y$ if substituted would again produce $y$. If you substitute $y$, you must substitute it by $g^{-1}f(x)$=$g^{-1}g(y)=y$. You can see you are again getting $y$.

Regarding your second problem: $S(m)=T(2^m)$

Let $y=m/2$

$$S(y)=T(2^y)$$

$$S(m/2)=T(2^{m/2})$$

You must substitute $m$ by $m/2$. What you are doing is dividing $2^m$ by $2$ which is completely wrong.

$\endgroup$
3
  • $\begingroup$ To avoid confusion, let's rename $T(2^m)$ to $S(t)$. Clearly $T(2^m) = 2T(2^{m/2}) + m$ should be $S(t) = S(t/2) + m$. But what the book says, it writes $S(t) = S(t/2) + t$ which confuses me. $\endgroup$ – M a m a D Oct 21 '17 at 14:26
  • $\begingroup$ If you replace $T(2^m)$ by S(t) then T($2^{m/2}$) would become S($t^{1/2}$). Hence you would get back your original equation S(t)=S($t^{1/2})$+m. $\endgroup$ – Kishan Kumar Oct 21 '17 at 17:04
  • $\begingroup$ You are taking different variables in T and S. That's what causing the problem. $\endgroup$ – Kishan Kumar Oct 21 '17 at 17:10

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