Lower Bound Omega Notation

Question

I have to prove that some number $S$ is bigger than $\Omega(|V|)$, where |V| is the number of vertices. I read the definition of asimptotic notations, but I am still confused with the examples. Fot example, in my case, I proved that $S \geq 1 + \frac{1}{2} + \frac{1}{3} + .... + \frac{1}{|V|}$. Am I done? Can someone give me similar examples of $\Omega$ functions?

Answer 1

No; what you have shown is that $S$ is bound from below by $H_{|V|}$, the $|V|^{th}$ harmonic number, which grows much more slowly than $|V|$.

I think you are misunderstanding $\Omega$ notation. Intuitively, if $S(G)$ is some function taking a graph to a (subset of) the reals, $S \in \Omega(|V|)$ states that $S$ grows at least as fast as the number of vertices, in the long run.

Formally, there are two (different) definitions of the $\Omega$ class of a function. First, $f(x)=\Omega(g(x))\ (x\rightarrow\infty)\;\Leftrightarrow\;\limsup_{x \to \infty} \left|\frac{f(x)}{g(x)}\right|> 0.$ This is the Hardy–Littlewood definition.

The second definition (which I find more useful and intuitive) is by Knuth: $f(x) = \Omega(g(x)) \iff g(x) = O(f(x))$.

You should figure out which is the appropriate definition for your setting.