0
$\begingroup$

Is there a standard way to find a $\Omega$ of a function $f(n)$ ?

I mean, I'm trying to understand how to determine:

$g(n)=\Omega(f(n))$

where $f(n)$ is a polynomial or logarithmic function

I understand the definition by which:

$g(n)=\Omega(f(n)) \iff g(n)\ge cf(n), n>n_0, c>0, n_0>0$

But I just can't understand what to do to get $g(n)$ given $f(n)$

Looking for examples I found that: $\log(n!) = \Omega(n\log(n))$

But I still can't understand how to explain that result and I'm not able to sort this out:

$n^2\log(n) = \Omega(??)$

Thanks in advance

  • 0
    The point is that $c$ and $n_0$ don't matter. You need some values for a particular problem, but we don't care what they are. All that matters is the behavio(u)r as $n \to \infty$. If you think only about polynomials, you only care about the order of the leading term. $.000001x^n \gt 10^{100}x^{n-1}$ eventually.2011-11-07

2 Answers 2

1

I suggest you apply these explanations about the $o$ and $O$ notations to the setting of the $\Omega$ notation. The take home message is that $\Omega(f(n))$ is in fact a class of sequences $(g(n))$ and not one particular sequence $(g(n))$. For example, if $g(n)=\Omega(f(n))$ (something which, in full rigor, should be denoted $g\in\Omega(f)$), then $ug(n)=\Omega(f(n))$ for every nonzero $u$.

A trivial remark is that $(f(n))$ always belongs to $\Omega(f(n))$ but many other sequences $(g(n))$ do as well (in general). In any case, since $f(n)=n^2\log(n)$ is a sequence you admit as a reference, your second case is solved by $n^2\log(n)=\Omega(n^2\log(n))$.

As regards your first example, defining $f(n)=\log(n!)$, an easy induction(1) yields $f(n)\geqslant\frac12n\log(n)$ for every $n\geqslant1$ hence $f(n)=\Omega(n\log(n))$.

(Or one can use the weak version of Stirling's approximation $\log(n!)=n\log(n)+o(n\log(n))$ and the general fact that $g(n)=f(n)+o(f(n))$ implies $g(n)=\Omega(f(n))$.)

Note

(1) If $f(n)=\log(n!)$, the induction step $f(n+1)-f(n)\geqslant\frac12\log(n+1)-\frac12\log(n)$ is equivalent to the inequality $n\log(1+1/n)\leqslant\log(n+1)$. Since $\log(1+x)\leqslant x$ for every $x$, the LHS is at most $1$ and the RHS is at least $\log(3)>1$ for every $n\geqslant2$. Since $f(1)=0$ and $f(2)=\log(2)=\frac12(2\log(2))$, this proves that the inequality $f(n)\geqslant\frac12n\log(n)$ holds for every $n\geqslant1$.

  • 0
    Thank you, this one really cleared a couple of things :)2011-11-07
0

Stirling's approximation gives you that $n!\approx(\frac{n}{e})^n$ so $\log{n!}\approx n\log n-n$ Since $\log n \to \infty$ the $n \log n$ dominates. For $n^2 \log n$ I don't have a simpler form. It dominates $n^2$ and is dominated by $n^{2+\epsilon}$

  • 0
    Thank you, now I get how the first e$x$ample was calculated2011-11-07