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)

  • 0
    What definition of $\omega$ are you using?2012-02-13
  • 0
    @Aryabhata : http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations2012-02-13
  • 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$.

  • 1
    Primes are not special. Any infinite set of naturals will do.2012-02-13
  • 1
    Indeed: $f(2n)=f(2n+1)=n^2$.2012-02-13
  • 0
    @Aryabhata : Can you explain a bit more how we know that this example of $f(n)$ falls within $w(n)$?2012-02-13
  • 1
    @pepsi: Try proving that $(n-1)^2$ is $\omega(n)$.2012-02-13
  • 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