0
$\begingroup$

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 Answers 1

1

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

  • 0
    Yes sorry my mistake, I was confused. I think I understand now. You chose a function g(n) such that in the infinity will be 0 or 1 (oscillating) and therefore the little-o definition doesn't apply.2012-11-06