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
    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...2012-12-18
  • 0
    $\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!2012-12-18
  • 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$.