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

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.

• You might want to try to adapt this MSE computation. The asymptotics are different (work term same complexity as recursive component vs. recursive component higher complexity than work term) but the calculation is fairly similar. In fact your case is simpler than the material at the link. – Marko Riedel Oct 17 '14 at 22:15

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.
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.$$