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.