How to solve the recurrence relation for tight asymptotic bound without using master theorem?

Question

I have the following recurrence in my problem: $$T(n)= 4T(n/2)+n.$$
I have solved it by substitution by assuming the upper bound $O(n^3)$ but in solving it for $O(n^2)$ i am having some problems.I know that this problem is more tightly bounded to $O(n^2)$. Following are the attempts made by me through induction:

Assume $$T(k)\leqslant ck^2, \mbox{ for } k.$$ Now we have
$$T(n)=4T(n/2)+n,$$ $$T(n)=4c(n^2/4)+n, \mbox{ from induction hypothesis as } n/2<n,$$ $$\ldots$$ $$T(n)=cn^2+n.$$

So in the end if i have to prove this tight bound the requirement becomes

$$cn^2 + n \leqslant cn^2.$$
Now i don't understand how to get out of this with induction not using the master theorem? I am a beginner in this so please forgive me if i have produced any syntatical errors. Thanks in advance.

Answer 1

The so-called master theorem is not needed anyway, neither here nor in many other questions of the same ilk asked on math.se so the fact that you require a solution not using it is quite welcome... Here we go:

Just as when studying ordinary differential equations, we start with the linear part of the relation, that is, $$T(n)=4T(n/2)=\color{blue}{2}^{\color{red}{2}}T(n/\color{blue}{2}),$$ or equivalently, $$\frac{T(n)}{n^{\color{red}{2}}}=\frac{T(n/2)}{(n/2)^{\color{red}{2}}},$$ which is obviously solved by $$T(n)=Cn^{\color{red}{2}},$$ for some constant $C$. This suggests to transform the relation at hand, using $$S(n)=T(n)/n^2.$$ One gets $$S(n)=S(n/2)+1/n.$$ Better, but not quite the best possible formulation... Iterating the identity involving $S$ yields the values of $S$ at $n/2$, $n/4$, and so on, hence we could as well consider from the start $$R(k)=S(2^k)=T(2^k)/4^k.$$ Now the relation at hand becomes $$R(k)=R(k-1)+1/2^k,$$ that is, $$R(k)=R(0)+1/2+1/4+\cdots+1/2^k=R(0)+1-1/2^k,$$ or equivalently, $$T(2^k)=4^k(T(1)+1)-2^k,$$ which proves that $$T(2^k)=\Theta(4^k),$$ for every nonnegative $T(1)$. And now comes one most unsatisfying practice of the field, which is to pretend that this last identity implies that $$T(n)=\Theta(n^2),$$ although it does not (and anyway, what would be the identity we started from when $n=3$?).

In retrospect, the exact formula we found suggests that the upper bound $$T(n)\leqslant Cn^2-n,$$ should carry through easily. And behold! if this upper bound holds for $n/2$, then $$T(n)=4T(n/2)+n\leqslant4(C(n/2)^2-(n/2))+n=Cn^2-n,$$ as desired. Likewise, every lower bound $$T(n)\geqslant cn^2-n,$$ is hereditary.

Answer 2

If $n=2^k$, then the recurrence $$T(n)=4T(n/2)+n,$$ becomes $$ T\big(2^{k}\big)=4T\big(2^{k-1}\big)+2^k, $$ and hence, if we set $S(k)=T\big(2^k\big)$, then $S(k)$ satisfies the recurrence relation $$ S(k)=4S(k-1)+2^k, $$ and therefore $$ \frac{S(k)}{4^k}=\frac{S(k-1)}{4^{k-1}}+2^{-k}. $$ Thus $$ \frac{S(k)}{4^k}=2^{-k}+2^{-k+1}+\cdots+2^{-1}+S(0)=S(0)+1-\frac{1}{2^k}, $$ and consequently $$ S(k)=4^k\big(S(0)+1\big)-2^k, $$ and finally, replacing back $n=2^k$ and $S(k)=T(n)$, we obtain $$ T(n)=n^2\big(T(1)+1\big)-n. $$