Prove that the little-o definition doesn't hold for two function (f and g)

218 Views Asked by At

I need your help with the following statement:

Show there exist two function $f(n), g(n)$ such that meet the following definition:

$g(n) = O(f(n))$ and $f(n) \ne O(g(n))$

But don't meet the little-o definition, that is :

Not for every $\epsilon >0$ there exist $n_0 \ge 1$ such that $g(n) \le \epsilon f(n)$ for every $n \ge n_0$

I'm not sure what way should I pick here.

It seems like every "Normal" two functions which meets the first definition also meets the little-o definition.

Thanks in advance!

1

There are 1 best solutions below

3
On BEST ANSWER

Just think of two functions $f$ and $g$, which are more or less "equal", but one of them (here: $g$) is to oszillating to bound the other. For example $f(n) = 1$ and $g(n) = \sin(n) + 1$.