Choosing Constant for Last Step in Substitution METHOD $T(n)= 5T(n/4) + n^2$ I figured out a solution to a recurrence relation, but I'm not sure what the constant should be for the last step to hold.
$T(n)= 5T(n/4) + n^2$
Guess: $T(n) = O(n^2)$
Prove: $T(n) \leq cn^2 $
Breakdown
$ T(n) \leq 5(c(n/4)^2) + n^2 $
$ = (5/16)cn^2 + n^2 $
$ \leq cn^2 $
For the last step to hold I'm not sure what the value of c should be because of the (5/16). My guess would be c &gt;= 1 and I'm not sure if that would hold.
Your constant $c$ needs to satisfy
$$ \frac{5}{16} c n^2 + n^2 \leq c n^2, $$
that is,
$$ \frac{5}{16} c + 1 \leq c. $$
Hopefully you can determine the set of constants $c$ for which this inequality is satisfied.