1
$\begingroup$

This question has already been asked, but I still cannot understand how the substitution makes sense in the recurrence equation $$T(n)=2T(\sqrt{n})+1$$

Following the logic:

  1. Substitute $n$ for $2^m$. This yields the equation:

$$ T(2^m)=2T(\sqrt{2^m})+1=2T(2^{m/2})+1 \\ \text{where } n = 2^m,\ m=\log_2 n $$ Great, this makes sense because we can substitute $n$ back in for $2^m$ and then we get the original equation.

  1. Now we introduce a new function $S(m)$ and we're going to say $S(m)$ = $T(2^m)$.

  2. I don't believe this implies $m=2^m$, because that would not make sense. So we're saying we're defining a new function $S$ that takes parameter $m$ and simply returns the function $T$ with parameter $2^m$: $$S(m) \rightarrow T(2^m)=2T(\sqrt{2^m})+1=2T(2^{m/2})+1 $$

  3. Fine, but since the $m$ is $S$ has no mathematical relationship to the $m$ in $T$, I'm going to rename $S(m)$ to be $S(x)$ to avoid confusion, so: $$S(x) \rightarrow T(2^m)=2T(\sqrt{2^m})+1=2T(2^{m/2})+1 $$

  4. Now if we pass $x/2$ into $S$, we get: $$ S(x/2) \rightarrow T(2^{x/2})=2T(\sqrt{2^{x/2}})+1=2T(2^{{x/2}/2})+1=2T(2^{x/4})+1 \\ $$

  5. Using the master theorem for $S(x/2)$, we get $O(\log x)$. However, since we have no equivalence of $x$ and $n$, then how do we substitute back to get $n$?


So this leads me to believe there must be some mathematical relationship between $S(m)$ and $T(2^m)$. If $2^m$ is substituted for $m$, I'm going to replace $x$ with $m$ again, because it doesn't make sense to me to use the same variable in a substitution and make it confusing.

  1. Therefore: $$ S(x) = T(2^m)=2T(\sqrt{2^m})+1=2T(2^{m/2})+1 \\ S(x/2) = T(2^{x/2})=2T(\sqrt{2^{x/2}})+1=2T(2^{{x/2}/2})+1=2T(2^{x/4})+1 \\ \text{where } x=2^m $$
  2. Now my problem with this is: If $x=2^m$, $m=\log x$, $m$ also equals $\log n$, therefore $\log x=\log n$, $n=x$.

If $x=n$ then $S(x/2)=\dots=2T(2^{n/4})+1$.

3. The master theorem says $S(x/2) = \Theta(log_2(x))$.

Now $x=n$, so $\Theta(\log_2 x)=\Theta(\log_2 n)$, which is the right answer for $T(n)$. However: $$ 2T(2^{n/4})+1 \neq 2T(\sqrt{n})+1. $$ So, how can we say that the Big O of $S(x/2)$ is equivalent to the Big O of $T(n)$?


I obviously know I'm wrong. But the correct answer to this problem makes the math seem "hacky" and arbitrary. I can't seem to grasp how the logic maintains its equivalence?

Can someone help me understand how my thinking is wrong? If so, is there anyway to explain this without using $S(m)=T(2^m)$ because in either case I don't understand what this actually means.

$\endgroup$
7
  • 1
    $\begingroup$ Step 4 is where you go wrong. The $m$ in $S(m)$ is the same $m$ as in $T(2^m)$ in fact you have defined that $S(m) := T(2^m)$. In Step 4 you should write something like: $S(m) = T(2^m) = 2T(2^{m/2}) + 1 = 2S(m/2)+1$. Notice that you can solve $S(m) = 2S(m/2)+1$ for O(S(m)) and then since $m = log(n)$: $S(T(n))=O(S(\log n))$ $\endgroup$
    – plshelp
    Sep 13, 2021 at 2:26
  • $\begingroup$ The mathematical relationship between $S(m)$ and $T(2^m)$ is: $S(m) = T(2^m)$. $\endgroup$ Sep 13, 2021 at 7:34
  • $\begingroup$ Another mathematical relationship, which is quite useful here, is: $T(n) = S(\log_2 n)$. $\endgroup$ Sep 13, 2021 at 7:39
  • $\begingroup$ you could simply say that T could be expressed as a fn. of m instead of as function of n where m=logn; ie T(s(m))=2T(s(m/2))+1 & s(m)= 2^m . Now you reach the solution T(s(m))= O(log(s(m)))=O(log(2^m)), you can substitute n=(2^m) getting T(n)=O(log n) $\endgroup$
    – ShAr
    Sep 13, 2021 at 9:58
  • $\begingroup$ I’m having trouble understanding how a we can arbitrarily decide S(m)=T(2^m) and how this then yields S(m/2) and then is somehow still equivalent to the original function $\endgroup$
    – Ietpt123
    Sep 13, 2021 at 14:03

2 Answers 2

0
$\begingroup$

Here is the logical form of the argument.

  1. The starting point is a function $T$ defined recursively.

(Comments: (1) Your definition misses a base case; (2) If you think of the input to $T$ as an integer, then $T$ is only defined for integers of the form $2^{2^k}$.)

  1. Using $T$, we define another function $S$ by $S(m) = T(2^m)$. This function satisfies the recurrence $S(m) = 2S(m/2) + 1$, with base case $S(1) = T(2)$.

(Here we assume that the input to $S$ is an integer; so $S$ is only defined for integers of the form $2^k$.)

  1. We find the asymptotic rate of growth of $S(m)$ to be $\Theta(m)$.

(In fact, $S(m)+1 = 2(S(m/2)+1)$, and so $S(m) = m(1 + S(1)) - 1$.)

  1. Since $T(n) = S(\log_2 n)$, we conclude that the asymptotic rate of growth of $T(n)$ is $\Theta(\log n)$.

(In fact, $T(2^m) = m(1 + T(2)) - 1$.)

$\endgroup$
0
$\begingroup$

The question is best answered with $n=2^{2^m}$ so that

$$T(2^{2^m})=2T(\sqrt{2^{2^m}})+1=2T(2^{2^{m-1}})+1.$$

This has the functional form

$$S(m)=2S(m-1)+1$$

and it is no big deal to find the solution of the homogeneous recurrence $S_h(m)=c\,2^m$ and a particular solution $S_p(m)=-1$.

Now,

$$S(m)=c\,2^m-1$$ is another way to write

$$T(2^{2^m})=c\,2^m-1$$ or

$$T(n)=c\,\log_2(n)-1.$$


As we can check,

$$2c\,(\log_2(\sqrt n)-1)+1=\frac22c\,\log_2(n)-2+1=c\,\log_2(n)-1.$$


The flaw in your reasoning is to think that "the $m$ in $S$ has no mathematical relationship to the $m$ in $T$". On the opposite it is the same variable, and $S(m)=T(2^{2^m})$ is an identity, also written $S(\log_2(n))=T(2^n)$ or $S(\log_2(\log_2(n)))=T(n)$, which does define $S$ uniquely in terms of $T$.

$\endgroup$

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.