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

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

-
So actually I'm taking advantage of the Big-O being "Partially ordered set". That is, using the missing property "Totality". Am I right? – SyndicatorBBB Nov 6 '12 at 13:32
The failure of "Totality" says that there are functions $f, g$ with $f \not\in O(g)$, $g \not\in O(f)$. – martini Nov 6 '12 at 13:41
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. – SyndicatorBBB Nov 6 '12 at 13:45