Is log(n!) = Θ(n·log(n))?

Understanding log(n!) = Θ(n·log(n)) in Algorithm Analysis

Explore the mathematical proof and intuition behind why the logarithm of n factorial is asymptotically equivalent to n times log n, a fundamental concept in algorithm complexity.

In the realm of algorithm analysis, understanding the growth rate of functions is paramount. Big-O notation, Big-Omega notation, and Big-Theta notation are used to classify algorithms based on how their running time or space requirements grow as the input size grows. One common expression that frequently appears in the analysis of sorting algorithms (like Merge Sort or Quick Sort) and combinatorial problems is log(n!). This article delves into proving the asymptotic equivalence log(n!) = Θ(n·log(n)), providing both mathematical rigor and intuitive understanding.

What do Θ (Big-Theta) and log(n!) Mean?

Before we dive into the proof, let's clarify the terms involved:

• Big-Theta (Θ) Notation: When we say f(n) = Θ(g(n)), it means that f(n) is asymptotically bounded both above and below by g(n). Formally, there exist positive constants c1, c2, and n0 such that for all n >= n0, 0 <= c1·g(n) <= f(n) <= c2·g(n). Essentially, f(n) grows at the same rate as g(n).

• n! (n factorial): This is the product of all positive integers less than or equal to n. So, n! = n * (n-1) * (n-2) * ... * 2 * 1.

• log(n!): This is the logarithm of n factorial. By logarithm properties, log(n!) = log(n * (n-1) * ... * 1) = log(n) + log(n-1) + ... + log(1).

flowchart TD
    A[Start with log(n!)] --> B{Expand Factorial}
    B --> C[log(n * (n-1) * ... * 1)]
    C --> D{Apply Logarithm Property}
    D --> E[log(n) + log(n-1) + ... + log(1)]
    E --> F[Compare to n·log(n)]
    F --> G{Prove Upper and Lower Bounds}
    G --> H[Conclusion: Θ(n·log(n))]
    H --> I[End]

Conceptual flow for proving log(n!) = Θ(n·log(n))

Proof of log(n!) = Θ(n·log(n))

To prove log(n!) = Θ(n·log(n)), we need to show both the upper bound (O) and the lower bound (Ω).

Part 1: Proving the Upper Bound (log(n!) = O(n·log(n)))

We need to find a constant c2 and n0 such that log(n!) <= c2·n·log(n) for n >= n0.

log(n!) = log(n) + log(n-1) + ... + log(1)

Since each term log(i) for i from 1 to n is less than or equal to log(n):

log(n!) = Σ_{i=1 to n} log(i) <= Σ_{i=1 to n} log(n)

log(n!) <= n * log(n)

Here, we can choose c2 = 1 and n0 = 1. Thus, log(n!) = O(n·log(n)).

Part 2: Proving the Lower Bound (log(n!) = Ω(n·log(n)))

We need to find a constant c1 and n0 such that log(n!) >= c1·n·log(n) for n >= n0.

log(n!) = log(n) + log(n-1) + ... + log(n/2) + ... + log(1)

Consider only the terms from i = n/2 to n. There are n - n/2 + 1 = n/2 + 1 such terms. For n >= 2, n/2 + 1 > n/2.

Each of these n/2 terms (approximately) is greater than or equal to log(n/2):

log(n!) >= Σ_{i=n/2 to n} log(i)

log(n!) >= (n/2) * log(n/2) (ignoring the +1 for simplicity, as it doesn't change asymptotic behavior)

Using logarithm properties: log(n/2) = log(n) - log(2)

log(n!) >= (n/2) * (log(n) - log(2))

log(n!) >= (n/2) * log(n) - (n/2) * log(2)

For sufficiently large n, (n/2) * log(n) dominates (n/2) * log(2). We can choose c1 = 1/4 (or any constant less than 1/2) and a sufficiently large n0 such that (n/2) * log(n) - (n/2) * log(2) >= (1/4) * n * log(n).

For example, if log(n) >= 2 * log(2), which means n >= 4, then log(n) - log(2) >= log(n)/2. So, (n/2) * (log(n) - log(2)) >= (n/2) * (log(n)/2) = (1/4) * n * log(n).

Thus, log(n!) = Ω(n·log(n)).

Conclusion

Since log(n!) = O(n·log(n)) and log(n!) = Ω(n·log(n)), by the definition of Big-Theta, we can conclude that log(n!) = Θ(n·log(n)).

Practical Implications in Algorithm Analysis

The equivalence log(n!) = Θ(n·log(n)) is crucial for analyzing the complexity of many algorithms:

1. Sorting Algorithms: Comparison-based sorting algorithms have a theoretical lower bound of Ω(n·log(n)). This lower bound is derived from the number of possible permutations of n elements, which is n!. Any comparison sort must perform enough comparisons to distinguish between all n! possible orderings. The number of comparisons k must satisfy 2^k >= n!, which implies k >= log(n!). Since log(n!) = Θ(n·log(n)), the lower bound for comparison sorts is Ω(n·log(n)). Algorithms like Merge Sort and Heap Sort achieve this optimal O(n·log(n)) complexity.

2. Combinatorics and Permutations: When dealing with problems involving permutations, the n! factor often appears. Taking the logarithm helps in analyzing the growth rate more manageably, especially when n is large.

3. Information Theory: The entropy of a set of n distinct items can be related to log(n!), representing the amount of information needed to uniquely identify one item from n possibilities.

import math

def calculate_log_factorial(n):
    if n < 0:
        raise ValueError("Factorial is not defined for negative numbers")
    if n == 0:
        return 0.0 # log(1!) = log(1) = 0
    
    log_fact = 0.0
    for i in range(1, n + 1):
        log_fact += math.log(i)
    return log_fact

def calculate_n_log_n(n):
    if n <= 0:
        return 0.0
    return n * math.log(n)

# Test cases
print(f"n=10: log(10!) = {calculate_log_factorial(10):.4f}, 10*log(10) = {calculate_n_log_n(10):.4f}")
print(f"n=100: log(100!) = {calculate_log_factorial(100):.4f}, 100*log(100) = {calculate_n_log_n(100):.4f}")
print(f"n=1000: log(1000!) = {calculate_log_factorial(1000):.4f}, 1000*log(1000) = {calculate_n_log_n(1000):.4f}")

# Output for n=10:
# log(10!) = 15.1044, 10*log(10) = 23.0259
# Output for n=100:
# log(100!) = 363.7394, 100*log(100) = 460.5170
# Output for n=1000:
# log(1000!) = 5912.1282, 1000*log(1000) = 6907.7553

# Note: The values are not equal, but their growth rates are the same.

Python code demonstrating the values of log(n!) and n·log(n) for various n. Notice how they scale similarly.