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.

Let $f(n) = \omega(n)$.

Then for all constants $c > 0$ there exists a constant $n_0$ such that $f(n + 1) - f(n) > c$ for all $n > n_0$.

The concept of Little-Omega is that the function must be increasing asymptotically at a rate faster than the bounding function. So if the bounding function is linear, then the difference between the two points in f(n) has to be greater than some constant.

I understand conceptually why this is true, but is there a way to prove this mathematically?

(note: this is not homework)

share|improve this question
    
What definition of $\omega$ are you using? –  Aryabhata Feb 13 '12 at 20:00
    
@Aryabhata : en.wikipedia.org/wiki/… –  pepsi Feb 13 '12 at 20:05
2  
I sort of doubt this is true. For example, take f(x) = 2^2^2^x if x isn't a power of Grahams's number, and f(x) = f(x-1) otherwise. –  Lopsy Feb 13 '12 at 20:07
add comment

1 Answer

up vote 2 down vote accepted

As Lopsy says, this isn't true.

Consider the function (with natural number domain) such that $f(n) = n^2$ whenever $n$ is not of the form $p+1$ for prime $p$.

And $f(p+1) = f(p)$, for every prime $p$.

We have that $f(n) \ge (n-1)^2$ and so $f(n) = \omega(n)$.

Whatever $n_0$ you pick, there will be a prime $p \gt n_0$ such that $f(p+1) - f(p) = 0 \lt c$.

share|improve this answer
1  
Primes are not special. Any infinite set of naturals will do. –  Aryabhata Feb 13 '12 at 20:28
1  
Indeed: $f(2n)=f(2n+1)=n^2$. –  Did Feb 13 '12 at 20:33
    
@Aryabhata : Can you explain a bit more how we know that this example of $f(n)$ falls within $w(n)$? –  pepsi Feb 13 '12 at 20:34
1  
@pepsi: Try proving that $(n-1)^2$ is $\omega(n)$. –  Aryabhata Feb 13 '12 at 20:38
    
@Aryabhata : Thank you. I'm justifying this conceptually by looking at it as f(n) still has to grow asymptotically faster than cn, but just not necessarily for every step. –  pepsi Feb 13 '12 at 20:57
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.