3
$\begingroup$

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)

  • 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.2012-02-13

1 Answers 1

2

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

  • 0
    @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.2012-02-13