Difficulty understanding in substution method

Question

I'm researching recursive functions. I see that there is a method to solve them known as substution method. It is used like $n = 2^m$ or $n= 2^k$

For example, in this question,

$$T(n) = n^2 + \frac{n}{2} - 1 + T\left(\frac{n}{2}\right)$$

I tried to substitute $n=2^m$, which yields the following recurrence:

$$S(m) := T(2^m)$$ $$S(0) = 1$$ $$S(m) = 4^m + 2^{m-1} - 1 + S(m-1)$$

How does it become $S(m-1)$? I would say $S(2^{k}*2^{-1})$. I don't understand it.

In the same way, in other question as well,

Use substitution

$$S(n) = T(2^n) =2T\left(\frac{2^n}2\right)+2^n = 2T(2^{n-1})+2^n = 2S(n-1)+2^n $$

I don't understand how it becomes $S(n-1)$.

Could you please explain it?

Answer 1

$$ T\left(2^{\log_2 n}\right) = T\left(2^{\log_2 n-1}\right)+n\left(n+\frac 12\right)-1 $$

now calling $\log_2 n = z$ we have

$$ T\left(2^z\right) = T\left(2^{z-1}\right)+2^z\left(2^z+\frac 12\right)-1 $$

so the recurrence can be recast as

$$ S(z)=S(z-1)+2^z\left(2^z+\frac 12\right)-1 $$

with solution

$$ S(z) = \frac{1}{3} \left(3\cdot 2^z+2^{2 z+2}-3 z-7\right)+c_0 $$

and finally we return to $T(n)$ backwards with $z = \log_2 n$ obtaining

$$ T(n) = \frac 13\left(4n^2+3n-7\right)-\log_2 n+c_0 $$

NOTE

After substitution, $S(z) = S\left(\log_2 n\right) = T\left(2^{\log_2 n}\right) = T(n)$.

Equivalently, considering now

$$ T(n) = T\left(\frac na\right)+f(n),\ \ \ a > 0 $$

taking the subset $n = a^m$ and submitting the recurrence to this subset we have

$$ T\left(a^m\right) = T\left(a^{m-1}\right)+f\left(a^m\right) $$

considering now $S(\cdot) = T\left(a^{(\cdot)}\right)$ for clearer writing, we follow with

$$ S(m) = S(m-1) + f(a^m) $$

with solution

$$ S(m) = \sum_{k=0}^m f(a^k) $$

and returning to the original formulation

$$ S(m)=T\left(a^m\right)=T(n) = \sum_{k=0}^{\log_a n} f(a^k) $$

Note that the recurrence $S(m)$ operates in a subset of $T(n)$ but at those points they have the same value.

Answer 2

You are seeking a canonical representation of the problem

$$ T(n)=T\bigg(\frac{n}{2} \bigg)+f(n) $$

where $f(n)$ is a polynomial in $n^k$. So, let's first consider the simpler monomial case of $f(n)=cn^k$. Using the substitution method discussed above, it can be shown that

$$ S(m)=S(0)+c\sum_{j=1}^m(2^k)^j=S(0)+c\frac{2^k}{2^k-1}\big(2^{km}-1\big) $$

and

$$ T(m)=T(1)+c\frac{2^k}{2^k-1}\big(2^{k\log_2 n}-1\big) $$

where it is understood that

$$ \lim_{k\to 0}\frac{2^k}{2^k-1}\big(2^{k\log_2 n}-1\big)=\log_2 n $$

It is now a short leap to show that for a polynomial,

$$ T(m)=T(1)+\sum_j c_j\frac{2^{k_j}}{2^{k_j}-1}\big(n^{k_j}-1\big) $$

In your case, we have $k=[0;1;2]$ and $c=[-1;1/2;1]$. I have verified this numerically, as well.

Answer 3

Consider a simpler case:

$$T(n)=T\left(\frac{n}{2}\right)+n$$

$T$ is a function of $n$ that satisfies the above equation for all values of $n$. Here comes the tricky part. Since the equation is valid for all values of $n$, in particular it is for $n=2^m$. The expression evaluated (we just replace n for $2^m$) is \begin{equation}\label{expression with m} T(2^m)=2^m+T\left(\frac{2^m}2\right)=2^m+T\left(2^{m-1}\right). \end{equation} You can now define a different, auxiliary function $S$. You may define it as $S(m)=T\left(2^m\right)$; that is, for every given value $m$, exponenciate 2 to $m$ and then evaluate $T$ at this new value. Now note that $S(m-1)=T(2^{m-1})$, because you take the value $m-1$, exponenciate $2$ to it, and then evaluate $T$ at this new value (this is how you defined $S$ in the first place). Reading some other comments I see that this part might be problematic to understand, so another way of seeing it is by simply defining a value $a=m-1$. Then, $S(m-1)=S(a)=2^a=2^{m-1}$-

Then, the equality above becomes $$S(m)=2^m+S(m-1).$$

The same reasoning can be used with the function you provided. Hope this helps!

Answer 4

We can consider the calculation as two-step approach. We start from \begin{align*} \color{blue}{T(n) = n^2 + \frac{n}{2} - 1 + T\left(\frac{n}{2}\right)} \end{align*}

First step: Substitution $n=2^m$

When we substitute $n=2^m$ we obtain by replacing each occurrence of $n$ with $2^m$: \begin{align*} T\left(2^m\right) &= \left(2^m\right)^2 + \frac{2^m}{2} - 1 + T\left(\frac{2^m}{2}\right)\\ &=4^m+2^{m-1}-1+T\left(2^{m-1}\right)\tag{1} \end{align*}

Second step: Introducing function $S$

We introduce a new function $S$, given for natural numbers $m$ as \begin{align*} \color{blue}{S\left(m\right)=T\left(2^m\right)}\tag{2} \end{align*}

In (2) we obtain by substituting $m$ with $m-1$: \begin{align*} \color{blue}{S\left(m-1\right)=T\left(2^{m-1}\right)}\tag{3} \end{align*}

From (2), (3) and (1) we conclude \begin{align*} T\left(2^m\right) &= 4^m+2^{m-1}-1+T\left(2^{m-1}\right)\tag{$\to\mathrm{(1)}$}\\ \color{blue}{S(m)}&\color{blue}{=4^m+2^{m-1}-1+S(m-1)}\tag{$\to\mathrm{(2),(3)}$} \end{align*} and the claim follows.