Big theta notation in substitution proofs for recurrences

Question

Often in CLRS, when proving recurrences via substitution, Ө(f(n)) is replaced with cf(n).

For example,on page 91, the recurrence

T(n) = 3T(⌊n/4⌋) + Ө(n^2)

is written like so in the proof

T(n) <= 3T(⌊n/4⌋) + cn^2

But can't Ө(n^2) stand for, let's say, cn^2 + n? Would that not make such a proof invalid? Further in the proof, the statement

T(n) <= (3/16)dn^2 + cn^2
<= dn^2

is reached. But if cn^2 +n was used instead, it would instead be the following

T(n)<= (3/16)dn^2 + cn^2 + n

Can it still be proven that T(n) <= dn^2 if this is so? Do such lower order terms not matter in proving recurrences via substitution?

Answer 1

Yes, it does not matter.

T(n) <= (3/16)dn^2 + cn^2 + n still less than or equal to dn^2 if n is big enough. Because as n goes to infinity, two sides of the equation have the same increasing rate (which is n^2), so the lower-order term will never matter if there is a constant number of lower-order terms in the cost function. But if there is not a constant number of them, that is a different story.

Edit: as n goes to infinity, you will find suitable d and c for T(n) <= (3/16)dn^2 + cn^2 + n to be less than or equal to dn^2, for example d = 2 and c = 1