I need an explanation for this solution about solving a non-homogenous recurrence relation.

Question

We have the following recurrence:

$ T\left( n\right) = \begin{cases} 1 &:n=1\\ 3T\left( \dfrac {n}{2}\right) +n &: n>1 \end{cases} $

They attempt to solve it by letting $t_i = 2^i$ to obtain $t_i = 3T(2^{i-1}) + 2^i = 3t_{i-1} +2^i$. Why we do this? What gives us the permission to do this also?

A common problem that I still see myself grappling to understand in mathematics are statements like these where they do something that is totally arbitrary and then validate its use because it gives the final correct solution.

For an analogy, It's like telling me that we are going to use a hammer to hit a nail but without explaining what a hammer is and then justifying its use by saying that it did the job and leaving me like that.

The next step in the solution is to find the characteristic polynomial. Which is found by using this formula $a_0t_n+...+a_n t_{n-k} = b^nq(n)$ ==> $(a_0x^k+...+a_n)(x - b)^{d+1}$ where $d$ is the degree of $q(n)$.

Following the above we obtain our characteristic polynomial $p(x) = (x-3)(x-2)$. Therefore our roots are $r_1 = 3$ and $r_2 = 2$ which allows us to rewrite $t_i$ as $t_i = C_1 3^i + C_2 2^i$. Our goal is now to find the value of the constants $C_1$ and $C_2$.

This where we see the benefit of letting $t_i = T(2^i)$

$t_0 = T(2^0) = T(1) = 1$

$t_1 = T(2^1) = T(2) = 3T(1) + 2 = 5$

This mean that we have $C_1 + C_2 = 1$ and $3C_1 + 2C_2 = 5$.

The rest of the problem is pretty straightforward. My confusion is more about the justification of using and letting $t_i$ than what we achieve with it.

UPDATE

I have another confusion they later say that because we use only the values of n which are of the power of 2 $T(n) = t_{log(n)}$. What does log n have to do here?

Answer 1

The problem is not well specified until we are told what to do when the division doesn't come out even. If we try to compute a few small values, $T(2)=3T(1)+2=5$ comes out easily, but $T(3)=3T(\frac 32)+3$ and we don't have a value to plug in for $T(\frac 32)$. Maybe we are supposed to round up, maybe we are supposed to round down. Whatever we do, computing $T(4)$ is again not a problem. $T(4)=3T(2)+4=24$.

They are just observing that we have the information to compute $T(2^i)$ as long as we have the lower powers of $2$. They put off until later determining what to do for other values of the argument. Doing this is fair, but when they fill in the other values you have to assess whether you believe that result. I would guess they want to extend the formula they get when $n$ is a power of $2$ to all $n$, but you didn't show that.

The statement $T(n)=t_{\log n}$ is derived from the way $t_i$ is defined. I believe you have misquoted it and it should be $t_i=T(2^i)$ When you plug that in you get the equation you quote, $t_i=3T(2^{i-1})+2^i$. We note that $i=\log_2 n$ to get $T(n)=t_{\log n}$, valid when $n$ is a power of $2$

Answer 2

Another way to solve it

$$ T\left(2^{\log_2 n}\right)=3T\left(2^{\log_2 \frac n2}\right)+n $$

now calling

$$ \mathbb{T}(\cdot)=T\left(2^{(\cdot)}\right),\ \ \ z = \log_2 n $$

we have

$$ \mathbb{T}(z)=3\mathbb{T}(z-1)+2^z $$

solving this recurrence we get

$$ \mathbb{T}(z)=2(3^z-2^z)+3^z C_0 $$

then

$$ T(n) = 2(3^{\log_2 n}-2^{\log_2 n})+3^{\log_2 n} C_0 $$

and as $T(1) = 1$ we have finally

$$ T(n) =3\times 3^{\log_2 n}-2n = 3 n^{\log_2 3}-2n $$