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

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)$$?

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.$$