Section 4.4 of Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein gives the following to verify that $O(n^2)$ is an upper bound for the recurrence $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$:

\begin{align} T(n) &\leq 3T(\lfloor n/4 \rfloor) + cn^2 \\ & \leq 3d \lfloor n/4 \rfloor^2 + cn^2 \\ &\leq 3d(n/4)^2 + cn^2 \\ &= \frac{3}{16} dn^2 + cn^2 \\ &\leq dn^2. \end{align}

How do I get $T(n) \leq 3T(\lfloor n/4 \rfloor) + cn^2$ from $T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2)$?


1 Answer 1


The equation $$ T(n) = 3T(\lfloor n/4 \rfloor) + \Theta(n^2) $$ has the following meaning: there exists a function $f(n) = \Theta(n^2)$ such that $$ T(n) = 3T(\lfloor n/4 \rfloor) + f(n). $$ Since $f(n) = \Theta(n^2)$, we can find a constant $c>0$ such that $f(n) \leq cn^2$, and so $$ T(n) \leq 3T(\lfloor n/4 \rfloor) + cn^2. $$


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.