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?
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?
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.
I hope this answers your question.