Choosing Constant for Last Step in Substitution METHOD $T(n)= 5T(n/4) + n^2$

Question

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 >= 1 and I'm not sure if that would hold.

Answer 1

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.

Answer 2

$$T(n)= 5T\left(\frac{n}{4}\right) + n^2 = 5^2T\left(\frac{n}{4^2}\right)+\left(\frac{5}{16}+1\right)n^2=\\=5^3T\left(\frac{n}{4^3}\right)+\left(\left(\frac{5}{16}\right)^2+\frac{5}{16}+1\right)n^2=\cdots=\\ =5^kT\left(\frac{n}{4^k}\right)+\left(\left(\frac{5}{16}\right)^{k-1}+\cdots +\frac{5}{16}+1\right)n^2$$ If you have some initial condition for $T(1)$ and we assume $n=4^k \Leftrightarrow k=\log_{4}n$, then we obtain $$T(n)=5^kT(1)+n^2\frac{16}{11}\left(1- \left(\frac{5}{16}\right)^{k-1}\right) \in O(n^2)$$