Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.