0

I'm trying to figure out the implications of $\Omega$ in asymptotic analysis. Let's say I have a function $f(n)=\Omega(n)$. From my understanding, and Asymptotic analysis: difference between big O and big Omega limits?

this implies the following:

$\exists c>0$, such that $\exists n_0 $ s.t. $\forall n \ge n_0, \,\, f(n) \ge cn$

In some literature, I've heard this described as "f(n) cannot be bounded by a constant". I'd like to know why that is the case. To me $f(n)=\Omega(n)$ seems to imply the following:

$\nexists c >0$, such that $\exists n_0 $ s.t. $\forall n \ge n_0, \,\, f(n) < cn$.

...which to me means its performance cannot be bounded by a linear function of $n$. i.e. $O(n) < f(n)$. How does this imply $f(n)$ cannot be bounded by a constant? Can't we say something stronger?

somewhere
  • 69
  • 1
    The table Family of Bachmann–Landau notations has the correct definitions. The first statement you write is correct (and the second incorrect). The answer to your question is your second statement is not correct. $f \in \Omega(n)$ is not the same as saying $f$ cannot be bounded above by a constant (though it does imply this). For instance, $\log(n)$ cannot be bounded above by a constant but is not in $\Omega(n)$. – Geoffrey Sangston Dec 01 '23 at 18:37
  • I think you're getting tripped up by your specific choice of a linear function rather than the more general g(n) cases shown in the tables GeoffreySangston linked. You're looking to prove whether you can find an example constant (maybe call it a "constant multiplier") $c$ satisfying $f(n)\geq c\cdot g(n)$, not specifically whether one can satisfy $f(n)\geq c$ (regardless of $g(n)$). – DotCounter Dec 01 '23 at 20:49
  • Very sorry guys - I made a big typo. The second statement was supposed to be not exists. It is fixed now, hopefully the question makes more sense.

    @GeoffreySangston, that's my confusion exactly. Why not say something stronger: Doesn't $f(n) \in \Omega(n)$ imply that $f(n)$ cannot be bounded by $O(n))$, and hence also cannot be bounded by $O(log(n))$, and cannot be bounded by $O(1)$? It seems like we can make a stronger statement.

     – somewhere Dec 02 '23 at 04:18
  • 1
    @somewhere $f \in \Omega(n)$ does not imply $f$ cannot be bounded above by $O(n)$. For instance, $n \in \Omega(n)$. A less trivial example is $n^2/(n+1) \in \Omega(n)$. Both of these functions are also in $O(n)$; i.e. $\Theta(n) := \Omega(n) \cap O(n)$ is a non-empty set. It is true that $f \in \omega(n)$ implies $f \notin O(n)$ (see table... also the equivalent limit definitions on the right may be helpful). And it is true that $f \in \Omega(n)$ implies $f \notin O(\log(n))$.

    I don't know how to answer why someone would or wouldn't say something stronger. Perhaps it was unnecessary.

     – Geoffrey Sangston Dec 02 '23 at 15:15

0 Answers0