# Incorrect inequality after verifying a recurrence solved using the master method

I am trying to solve the recurrence

$$T(n) = 4 T \Big( \frac{n}{2} \Big) + n .$$

using the master method and got $\Theta(n^2)$ using the first case theorem:

If $f(n) = O(n^{\log_{b}a-\epsilon})$ for some constant $\epsilon > 0$, then $T(n) = \Theta \left(n^{\log_b a} \right)$.

However when I verify the upper bound using the substitution method it seems I arrive at a contradiction:

After assuming that $T \left( \frac{n}{2} \right) \leq c(\frac{n}{2})^{2}$ and then substituting I get

\begin{align*} T(n) &= 4c \left( \frac{n}{2} \right)^2 + n \\ T(n) &= 4c \cdot \frac{n^2}{4} + n \\ T(n) &= cn^{2}+ n \leq cn^2 , \end{align*} which is obviously a contradiction.

Obviously there is something I am not seeing here or overlooked. Would like to have it pointed out.

-
What makes you think we will be able to guess which theorem you assigned the number $1$ to? – joriki Dec 12 '11 at 14:06
@joriki Sorry about that, I edited the question now. – Jeune Dec 12 '11 at 14:18

You are assuming $T(\frac{n}{2})=c(\frac{n}{2})^2$ and trying to prove $T(n) \le cn^2$.

Instead, you can only obtain that $T(n)=4T(\frac{n}{2})+n \le cn^2+n$, which does not contradict anything.

Hint. To actually prove this, you might want to try a different inductive hypothesis, perhaps a quadratic polynomial in $n$.

-
Of course I have to assume first that T($\frac{n}{2}$) $\leq$ c$(\frac{n}{2})^{2}$. Isn't that how the induction works first? – Jeune Dec 12 '11 at 14:24
Sure, but then you only obtain $T(n)\le cn^2+n$, which is not in contradiction with $T(n) \le cn^2$. – Peteris Dec 12 '11 at 14:28

If $H_k$ is the hypothesis that $T(2^k)=c4^k-2^k$, then, for every $k\geqslant0$, $H_k$ implies $H_{k+1}$. Since $H_0$ holds for $c_T=T(1)+1$, this proves that, for every $k\geqslant0$, $$T(2^k)=c_T4^k-2^k.$$ To deal with indices which are not powers of $2$, one must assume the following:

The sequence $(T(n))_n$ is nondecreasing.

Then, for every $n\geqslant1$, there exists $k$ such that $2^k\leqslant n\lt2^{k+1}$, hence $$T(n)\leqslant T(2^{k+1})= c_T4^{k+1}-2^{k+1}\leqslant4c_T4^{k}\leqslant4c_Tn^2.$$ Likewise, $4^k\gt\frac14n^2$ and $2^k\leqslant n$ hence $$T(n)\geqslant T(2^k)=c_T4^k-2^k\geqslant\tfrac14c_Tn^2-n.$$ Finally, for every $n\geqslant1$, $$\tfrac14c_T^2n^2-n\leqslant T(n)\leqslant4c_Tn^2,$$ and $n=o(n^2)$, hence $T(n)=\Theta(n^2)$.

-
And I would not use contradiction in the title, if I were you. – Did Dec 12 '11 at 14:47
If I use the H(n) you gave as a hypotheses I get T(n) $\leq$ (c-1)$n^{2}$ + n. How can I now say that T(n) = O($n^{2}$)? – Jeune Dec 12 '11 at 15:22
Certainly not. See edit. – Did Dec 12 '11 at 15:35
+1 that's an interesting answer. It makes sense to me that T(n) $\leq$ $c_{1}$ $n^{2}$ -n $\leq$ $c_{1}$ $n^{2}$. However I do not understand how $2^{k}$ suddenly came into the picture. – Jeune Dec 12 '11 at 16:17
Since one relates $T(n)$ to $T(2n)$, the fact that the powers of $2$ enter the picture is not very surprising, I would say. Likewise, one could consider $(T(3\cdot2^k))_{k\geqslant0}$ or $(T(5\cdot2^k))_{k\geqslant0}$, and so on. But there is no way to get a relation between $T(1)$ and $T(3)$, for example, which is why I added the hypothesis that $(T(n))_{n\geqslant1}$ is nondecreasing. Otherwise, one is stuck with different problems, each concerning a sequence $(T((2i+1)\cdot2^k))_{k\geqslant0}$, for some $i\geqslant0$. – Did Dec 12 '11 at 17:24