Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

On page 9 (70) in

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|cite|improve this question
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
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|cite|improve this answer
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


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.