0

$f(n)=O(g(n))$ and $f(n),g(n)>0$ for $n ≥ 1$, then there is a constant c such that $0 ≤ f(n) ≤ c·g(n)$ for $n ≥ 1$

jack90
  • 3

2 Answers2

0

$f(n)=O(g(n))$ means that $(\frac{f(n)}{g(n)})$ is a bounded sequence.

Fred
  • 77,394
0

I assume you mean $f,g:\Bbb N\to\Bbb R$. Consider $N$ and $c'$ coming from the definition of $f\in O(g)$.

$c'$ covers all the values $n\ge N$. For $1\le n<N$, call $c_n=\frac{f(n)+1}{g(n)}$. Then, $c=\max\{c',c_1,c_2,\cdots, c_{N-1}\}$ works for all $n\ge1$.

On the other hand, for $f\ge0$ and $g>0$ your condition clearly implies $f\in O(g)$.