# Want to show that $T(n)\leq dn^2$

On page 9 (70) in http://russell.lums.edu.pk/~cs211aw07/slides/clrs-rec.pdf

they try to argue that $T(n) \leq d n^2$ using the substitution method. Someone who can explain in details why $cn^2$ in the last step disappears?

-
Hi user11775: I tried to answer your question below. In the future, please try to make your questions self-contained so that potential answerers don't need to click a link to see what you're actually asking. Like this, you'll also get better and quicker answers, so this is in everyone's interest. – t.b. Jun 6 '11 at 12:02

If I understand correctly, the question is why

$$\frac{3}{16}d n^2 + cn^2 \leq dn^2$$

holds for $d \geq \frac{16}{13} c$, where $c,d \gt 0$ are some constants.

To see this, note that $c \leq \frac{13}{16}d$, hence

$$\frac{3}{16}d n^2 + c n^2 \leq \frac{3}{16}d n^2 + \frac{13}{16}d n^2 = \frac{3+13}{16}d n^2 = d n^2$$

as we wanted.

In fact, if we want $\frac{3}{16}dn^2 + cn^2 \leq dn^2$ to hold for all $n \geq 1$, then dividing this inequality by $n^2$ gives $\frac{3}{16} d + c \leq d$ and thus $c \leq d - \frac{3}{16}d = \frac{13}{16}d$. Solving for $d$ then yields $d \geq \frac{16}{13}c$ which shows that this estimate is best possible, in fact.