2
$\begingroup$

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?

  • 2
    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.2011-06-06

1 Answers 1

3

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.

  • 0
    @user11775: You're welcome, o$f$ course! I'm glad I was able to help.2011-06-06