How do I get $T(n) \leq 3T(\lfloor n/4 \rfloor) + cn^2$ from $T(n) = 3T(\lfloor n/4 \rfloor) + cn^2$?

Question

Section 4.4 of Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein gives the following to verify that $O(n^2)$ is an upper bound for the recurrence $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$:

\begin{align} T(n) &\leq 3T(\lfloor n/4 \rfloor) + cn^2 \\ & \leq 3d \lfloor n/4 \rfloor^2 + cn^2 \\ &\leq 3d(n/4)^2 + cn^2 \\ &= \frac{3}{16} dn^2 + cn^2 \\ &\leq dn^2. \end{align}

How do I get $T(n) \leq 3T(\lfloor n/4 \rfloor) + cn^2$ from $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$?

Answer 1

The equation $$ T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2) $$ has the following meaning: there exists a function $f(n) = \Theta(n^2)$ such that $$ T(n) = 3T(\lfloor n/4 \rfloor) + f(n). $$ Since $f(n) = \Theta(n^2)$, we can find a constant $c>0$ such that $f(n) \leq cn^2$, and so $$ T(n) \leq 3T(\lfloor n/4 \rfloor) + cn^2. $$