Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  t.b. Jun 6 '11 at 12:02

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
1  
Thank you so much!! –  user11775 Jun 6 '11 at 12:36
    
@user11775: You're welcome, of course! I'm glad I was able to help. –  t.b. Jun 6 '11 at 12:38

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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