# Functions that are $\omega$(n)

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)

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

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

-
Primes are not special. Any infinite set of naturals will do. – Aryabhata Feb 13 '12 at 20:28
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
@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