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.

Improve this question
$\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$ Commented Sep 13, 2021 at 2:26
  • $\begingroup$ The mathematical relationship between $S(m)$ and $T(2^m)$ is: $S(m) = T(2^m)$. $\endgroup$ Commented Sep 13, 2021 at 7:34
  • $\begingroup$ Another mathematical relationship, which is quite useful here, is: $T(n) = S(\log_2 n)$. $\endgroup$ Commented 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$ Commented 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$ Commented Sep 13, 2021 at 14:03

2 Answers 2

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

Improve this answer
$\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$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.