Simplifying Notations in Recurrence Relation

Question

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.
• AlessandroF: @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 :-)

Answer 1

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.

• AlessandroF: 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?
• user16034: @AlessandroF: they are computing an upper bound.