How can I prove that if $f(n) = O(1)$ leads to $f(n) = \Omega(1)$ as well?
I need a Formal definition of the meaning that a function $f(n) = O(1)$
Asked
Active
Viewed 149 times
0
-
1Are there any other definitions but formal ones? – Hagen von Eitzen Apr 14 '15 at 10:53
-
I meant the calculus meaning, with $lim$ not the regular definition. – ThunderWiring Apr 14 '15 at 10:56
1 Answers
0
The formal definition of $f(n)=O(1)$ is that there exists $M$ such that for all sufficiently large $n$ (for it is implicit that we consider $n\to\infty$) $|f(n)|\le M|1|$. If $f$ is only defined on $\mathbb N$ anyway, this is equivalent with: $f$ is bounded.
The Hardy-Littlewood definition of $f(x)=\Omega(1)$ would mean that $\limsup_{n\to\infty}\left|\frac{f(n)}{1}\right|>0$. Note that with this definition, $f(n)=O(1)$ does not imply $f(n)=\Omega(1)$: Just consider $f(n)=\frac1n$. Knuth uses a stronger definition, namely that $1=O(f(n)$ - which does not follow either.
Hagen von Eitzen
- 374,180
-
In what sense is Knuth's definition stronger? If $c := \limsup |f(n)| > 0$, we have that finally $|f(n)| > \frac c2$. That is, finally $1 \le \frac 2c|f(n)|$ or $1 = O(f)$. – martini Apr 14 '15 at 11:09
-
@martini No, we only have tat $|f(n)|>\frac c2$ infintiely often. For example $f(n)=1+(-1)^n$ is $\Omega(1)$ in the Hardy-Littlewood sense, but not $\Omega(1)$ in the Knuth sense – Hagen von Eitzen Apr 14 '15 at 11:54