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

Question

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?

Answer 1

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