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.

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|improve this question
add comment

2 Answers

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|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
add comment

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|improve this answer
add comment

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.