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

Improve this question
$\endgroup$
5
  • $\begingroup$ What is your question? What specifically don't you like about other answers? $\endgroup$
    – Raphael
    Commented Oct 21, 2017 at 16:18
  • $\begingroup$ Another duplicate. $\endgroup$
    – Raphael
    Commented Oct 21, 2017 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
    Commented Oct 21, 2017 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
    Commented Oct 21, 2017 at 16:24
  • $\begingroup$ @Raphael It's not a duplicate. I was stuck on S(m)=2S(m/2)+m with the last m not renaming problem either. Please remove your flag if possible. $\endgroup$
    – xianshenglu
    Commented Sep 11, 2022 at 16:50

1 Answer 1

Reset to default
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.

Improve this answer
$\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
    Commented Oct 21, 2017 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
    Commented Oct 21, 2017 at 17:04
  • $\begingroup$ You are taking different variables in T and S. That's what causing the problem. $\endgroup$
    – Kishan Kumar
    Commented Oct 21, 2017 at 17:10

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