2
$\begingroup$

I'm determining if $\sum_{i=1}^{n} \log(i)$ is the $ \Omega (n\log n)$.

The summation of the above,$$\sum_{i=1}^{n} \log(i)= \log n!\approx n\log n$$

And checking with big omega

$$n\log n \geq c \times n\log n$$

Therefore since $n\log n$ will always be smaller than $c \times n\log n$ , $\sum_{i=1}^{n} \log(i)$ cannot be the $ \Omega (n\log n)$.

Is this logic correct?

$\endgroup$
6
  • 1
    $\begingroup$ Note that $$\sum_{i=1}^n\log i\leqslant \sum_{i=1}^n\log n=n\log n$$ $\endgroup$
    – Pedro
    Nov 1, 2013 at 21:57
  • 1
    $\begingroup$ $\log n! \sim n \log n$ by Stirling's formula, so the weaker statement $\log n! = \Omega(n\log n)$ is certainly true. $\endgroup$ Nov 2, 2013 at 0:06
  • $\begingroup$ Could you clarify what you are asking? Are you confused about the definition of $\Omega(\cdots)$? $\endgroup$ Nov 2, 2013 at 4:43
  • $\begingroup$ The question is, ...is logn! the big omega of nlogn Ω(nlogn)? if so provide a derivation to prove it's true. $\endgroup$
    – GivenPie
    Nov 2, 2013 at 16:54
  • $\begingroup$ Do you understand why $n\log n \in \Omega(n\log n)$? $\endgroup$ Nov 2, 2013 at 17:58

1 Answer 1

2
$\begingroup$

A review of Big Omega notation.

Suppose the functions $f$ and $g$ are defined on the natural numbers $\mathbb{N}$. The statement

$f(n) \in \Omega(g(n))$ as $n \to \infty$

is defined to mean that we can find a $C > 0$ and an $N \in \mathbb{N}$ such that

$$ |f(n)| \geq C|g(n)| $$

for all $n \geq N$.

For example,

$$ \begin{align} \left|n^2-n\right| &= n^2 - n \\ &\geq n^2 - \frac{n^2}{2} \\ &= \frac{n^2}{2} \\ &= \frac{1}{2} \left|n^2\right| \end{align} $$

for all $n \geq 2$. By taking $C = 1/2$ and $N = 2$ we can rewrite this statement as

$$ \left|n^2-n\right| \geq C \left|n^2\right| $$ for all $n \geq N$.

This satisfies the definition of the Big Omega, so we may conclude that $n^2-n \in \Omega(n^2)$ as $n \to \infty$.

As another example, it is always true that

$$ |f(n)| \geq |f(n)| $$

for any $f$ and any $n$. By taking $C = 1$ and $N = 1$ we can rewrite this as

$$|f(n)| \geq C|f(n)|$$ for all $n \geq N$.

This also satisfies the definition of Big Omega, so we may conclude that $f(n) \in \Omega(f(n))$ as $n \to \infty$.

The problem at hand.

We are interested in finding the Big Omega classification of the sum

$$ f(n) = \sum_{i=1}^{n} \log i. $$

Since the $\log$ function is increasing we have, for $n \geq 1$,

$$ \begin{align} \int_1^n \log x\,dx &= \sum_{i=1}^{n-1} \int_{i}^{i+1} \log x\,dx \\ &\leq \sum_{i=1}^{n-1}\int_{i}^{i+1} \log(i+1)\,dx \\ &= \sum_{i=1}^{n-1} \log(i+1) \\ &= \sum_{i=1}^{n} \log i. \end{align} \tag{1} $$

Now we want to find the Big Omega classification of

$$ g(n) := \int_1^n \log x\,dx = n\log n - n + 1. $$

There are a couple of ways to do this. One is to notice that the dominant term of $g(n)$ is $n\log n$ — in fact we have

$$ \lim_{n\to\infty} \frac{g(n)}{n\log n} = \lim_{n\to\infty} \left(1 - \frac{1}{\log n} + \frac{1}{n\log n}\right) = 1. $$

So if we fix $0 < C < 1$ (for instance fix $C = 1/2$) then we can find an $N \in \mathbb{N}$ such that

$$ \frac{g(n)}{n\log n} \geq C $$

for all $n \geq N$. Since $n\log n > 0$ for $n \geq N$ we can rearrange this inequality to get

$$ g(n) \geq Cn\log n $$

for all $n \geq N$. Note that $g(n) > 0$, so this is equivalent to the statement that $|g(n)| \geq C|n\log n|$ for $n \geq N$.

That was certainly the easy way to show that $g(n) \in \Omega(n\log n)$ as $n \to \infty$. A slightly less general approach is to observe that

$$ \begin{align} g(n) &= n\log n - n + 1 \\ &> n\log n - n \\ &\geq n\log n - \frac{1}{2} n\log n \\ &= \frac{1}{2}n\log n \end{align} $$

for all $n \geq \left\lceil e^2 \right\rceil$.

Okay, so we know that $g(n) \in \Omega(n\log n)$ as $n \to \infty$. We proved above that $f(n) \geq g(n)$ for $n \geq 1$, and since they are both positive this actually means that $f(n) \in \Omega(g(n))$ as $n \to \infty$. Thus

$$ f(n) \in \Omega(g(n)) \quad \wedge \quad g(n) \in \Omega(n\log n) \quad \Longrightarrow \quad f(n) \in \Omega(n\log n) $$

as $n \to \infty$ by transitivity of $\Omega$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.