# Is this true or false: $\sum_{i=1}^{n} \log(i)$ is the $\Omega (n\log n)$?

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?

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

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$.