1
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Commented Apr 22, 2022 at 12:41
  • $\begingroup$ @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 :-) $\endgroup$
    – AlessandroF
    Commented Apr 22, 2022 at 13:07

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – AlessandroF
    Commented Apr 22, 2022 at 13:02
  • $\begingroup$ @AlessandroF: they are computing an upper bound. $\endgroup$
    – user16034
    Commented Apr 22, 2022 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.