Show That the Sum of log(i) from 1 to n Is O(n log n)

Let

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

To show that $S_n$ is $O(n\log n)$, bound each term by the largest one. Since the logarithm is increasing, $\log(i) \leq \log(n)$ whenever $1 \leq i \leq n$. There are $n$ terms, so the sum is at most $n\log(n)$. This proves the requested upper bound directly.

The same sum has a useful exact interpretation: $S_n = \log(n!)$, by the logarithm rule that turns a product into a sum. An integral comparison shows that its growth is not merely bounded above by $n\log n$; it is of that order.

Direct proof of the upper bound

Assume the logarithm has a fixed base greater than 1, so it is increasing. For every integer $i$ from 1 through $n$,

$$\log(i) \leq \log(n).$$

Summing these $n$ inequalities gives

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

Big O notation allows a constant factor in the upper bound. Here the inequality even holds with constant 1 for every positive integer $n$ (including $n=1$, where both sides are zero). Therefore $S_n = O(n\log n)$.

The logarithm base does not affect the asymptotic result. Changing from base $b$ to base $a$, where both are greater than 1, multiplies every logarithm by the fixed constant $\log_a(b)$. Big O and Big Theta growth rates are unchanged by such a constant factor.

Why the bound is tight

To establish a matching lower bound, use the fact that $f(x)=\log(x)$ is increasing. With the natural logarithm, on each interval $[i-1,i]$ for $i=2,\ldots,n$, the function is no larger than $\log(i)$. Thus

$$\begin{aligned} \sum_{i=1}^{n}\ln(i) &\geq \int_{1}^{n}\ln(x)\,dx \\ &= n\ln(n)-n+1. \end{aligned}$$

For sufficiently large $n$, the right-hand side is at least a positive constant times $n\ln(n)$. For example, when $n\geq 5$, $n\ln(n)-n+1 \geq \tfrac{1}{2}n\ln(n)$. The upper bound is $n\ln(n)$, so together these show

$$\sum_{i=1}^{n}\ln(i) = \Theta(n\ln(n)).$$

The same conclusion holds for any fixed logarithm base greater than 1. The integral is just a convenient way to establish the lower bound; it is not needed for the original Big O proof.

Worked example

Take $n=8$ and use natural logarithms. The sum can be evaluated using the factorial identity:

$$\begin{aligned} \sum_{i=1}^{8}\ln(i) &= \ln(1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7\cdot8) \\ &= \ln(8!) \\ &= \ln(40320) \\ &\approx 10.605. \end{aligned}$$

The simple upper bound gives $8\ln(8) \approx 16.636$, so the sum is indeed below $n\ln(n)$. The bound need not be an equality: Big O describes how the sum grows as $n$ increases, not its exact value for each $n$.

Common mistakes

• Treating the sum as $n$ identical terms. The terms differ, but each is no greater than $\log(n)$; this is what makes the term-by-term bound valid.
• Confusing an upper bound with an exact formula. The expression $n\log(n)$ is a convenient bound, not the value of the sum. The exact value is $\log(n!)$.
• Claiming $O(n\log n)$ without specifying the logarithm convention. In algorithm analysis, the base is usually fixed and greater than 1. Its choice changes only a constant factor.
• Forgetting the tightness question. The direct comparison proves Big O. The integral comparison supplies a lower bound, which justifies the stronger statement $\Theta(n\log n)$.

If this sum appears in an algorithm analysis, you can use $O(n\log n)$ as an upper bound. When you need a tight asymptotic description, use $\Theta(n\log n)$.