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

1 Answer

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. – 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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 23, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9265352487564087, "perplexity_flag": "middle"}