Big theta notation in substitution proofs for recurrences Often in CLRS, when proving recurrences via substitution, $\Theta(f(n))$ is replaced with $cf(n)$.
For example, on page 91, the recurrence
$$ T(n) = 3T(⌊n/4⌋) + \Theta(n^2) $$
is written like so in the proof
$$ T(n) \le 3T(⌊n/4⌋) + cn^2. $$
But can't $\Theta(n^2)$ stand for, let's say, $cn^2 + n$? Would that not make such a proof invalid?
Further in the proof, the statement
\begin{align}
T(n) &amp;\le (3/16)dn^2 + cn^2 \\
     &amp;\le dn^2
\end{align}
is reached. But if $cn^2 + n$ was used instead of $cn^2$, that step would instead be the following
$$ T(n) \le (3/16)dn^2 + cn^2 + n $$
Can it still be proven that $T(n) \le dn^2$ if this is so? Do such lower order terms not matter in proving recurrences via substitution?
By definition, a function $f(n)$ is $\Theta(n^2)$ if there exist constant $b,c,N$ such that for all $n \geq N$,
$$ bn^2 \leq f(n) \leq cn^2.$$
In particular, as long as $n \geq N$, we can always replace $f(n)$ by $cn^2$ when upper-bounding an expression.
In your example of $cn^2 + n$, when $n \geq 1$ we have $n \leq n^2$ and so $cn^2 \leq (c+1)n^2$.