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

How can I find a $c$ such that $f_{2}(n) \leq c \cdot f_{3}(n)$?

where $f_{2}(n) = 2n + 20$ and $f_{3}(n) = n + 1$.

This was from the textbook, Algorithms (explaining something else), but I was wondering how they got the following: $$\frac{f_{2}(n)}{f_{3}(n)} = \frac{2n+20}{n+1} \leq 20$$

share|cite|improve this question
up vote 3 down vote accepted

your RHS is $2+\frac{18}{n+1}$ so $\frac{18}{n+1}\leq 18 \ \forall n\geq 0$

I hope it's now clear where the result comes from!

share|cite|improve this answer
sorry :( it's not, how did you get that? and you got 18 not 20 right? it's been a while since I've done math... – eddieberklee Dec 18 '12 at 23:28
$\frac{18}{n+1}$ is greatest when $n=0$ in that case it is 18, right? but $\frac{2n+20}{n+1}= 2+ \frac{18}{n+1}$ which is then greatest for $n=0$ i.e. its maximum value is 20!! so it is always smaller than 20 by definition of maximum value! – Moritzplatz Dec 18 '12 at 23:34
Oh, got it! Thank you – eddieberklee Dec 19 '12 at 2:22

In another way of putting Moritzplatz's correct answer:

Rewrite $2n+20 \le c(n+1)$,

$2+18/(n+1)\le c$.

The LHS is greatest and is $20$ when $n=0$.

share|cite|improve this answer

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.