3
$\begingroup$

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$

2 Answers 2

3

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!

  • 0
    Oh, got it! Thank you2012-12-19
3

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$.