# Simplifying Notations in Recurrence Relation

In the CLRS book, section 4.4 they try to resolve the following recurrence:

$$T(n) = 3T\bigg(\bigg\lfloor \frac{n}{4} \bigg\rfloor\bigg) + \Theta(n^2)$$

Later, they write the same recurrence as

$$T(n) = 3T\bigg(\frac{n}{4}\bigg) + cn^2$$

And I do not understand why they change $$\Theta(n^2)$$ to $$cn^2$$

Mathematically speaking, Theta is a set, while $$cn^2$$ is a number. Furthermore I know that $$cn^2 \in \Theta(n^2)$$ but not every polynomial in $$\Theta(n^2)$$ is in the form $$cn^2$$.

I'd enjoy to have a mathematical proof of what they did is correct, even if it's "easy to see", but I'm not satisfied with that.

Update
For whoever might be interested in the same question and seek for an answer, other than the given answers, I wrote a document here: https://www.overleaf.com/read/npvdnwyfxpcb

• While your rigorous attitude are praiseworthy, it should not prevent you from reading a few more pages down the stream. Your concern will be resolved. Commented Apr 22, 2022 at 12:41
• @JohnL. Thank you for your comment. I might have an older edition or maybe I don't have enough neurons, but I don't see any explaination about this. The book proceeds to show that the result of this specific case is correct by doing a substitution, where I'd love to understand mathematically why in general it works :-) Commented Apr 22, 2022 at 13:07

You may consider

$$T(n) -3T(\lfloor n/4 \rfloor) = \Theta(n^2)$$

which means that for some $$N$$, $$n>N$$ implies

$$T(n) -3T(\lfloor n/4 \rfloor) \le cn^2.$$

And if $$n$$ is a power of $$4$$, you may drop the floor:

$$T(n) -3T(n/4) \le cn^2.$$

These transformations are meant to make the resolution more tractable, and will not impair the final conclusions.

• Thank you very much Yves. So you showed that $T(n) \leq 3T(n/4) + cn^2$ but in the book there's an equal sign, is that good anyways? Commented Apr 22, 2022 at 13:02
• @AlessandroF: they are computing an upper bound.
– user16034
Commented Apr 22, 2022 at 13:14