Problem 7 - Discrete Mathematics with Applications

Question

Using the big-oh notation, estimate the growth of each function. $$f(n)=\lg (5 n) !$$

Step-by-Step Solution

Answer

The growth of the function \(f(n) = \lg(5n)!\) can be estimated as \(O(5n \lg{(5n)})\) using the big-oh notation.

Step 1: Understanding the factorial function

The factorial function has the following definition: \[n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1\] For example, \(4! = 4 \times 3 \times 2 \times 1 = 24\). We need to find \((5n)!\) in terms of its growth.

Step 2: Understanding the logarithm function

The logarithm function is denoted as \(\lg(x)\) in this exercise. Logarithmic functions grow relatively slowly compared to other growth rates, such as polynomial or exponential growth. In this case, we need to analyze \(\lg(5n)!\) as a whole to obtain its growth rate.

Step 3: Applying Stirling's approximation

Using the Stirling's approximation, we know that: \[n! \approx \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n\] Applying Stirling's approximation for our given function: \[(5n)! \approx \sqrt{2 \pi (5n)} \left(\frac{5n}{e}\right)^{5n}\]

Step 4: Taking the logarithm of Stirling's approximation

Taking the logarithm of the Stirling's approximation: \[\lg{(5n)!} \approx \lg{\left(\sqrt{2 \pi (5n)} \left(\frac{5n}{e}\right)^{5n}\right)}\] Using logarithm properties, we can rewrite the above expression as: \[\lg{(5n)!} \approx \frac{1}{2} \lg{(2 \pi (5n))} + 5n \lg{\left(\frac{5n}{e}\right)}\]

Step 5: Analyzing the growth rate and applying the big-oh notation

In this case, the slowest growing part is \(\frac{1}{2} \lg{(2 \pi (5n))}\) and the fastest growing part is \( 5n \lg{\left(\frac{5n}{e}\right)}\). Since we are interested in the growth rate, we can ignore the slowest growing part and focus on the fastest growing part. Thus, the function \(f(n) = \lg{(5n)!}\) has a growth rate of \(O(5n \lg{(5n)})\). Hence, the growth of \(f(n)\) can be estimated as \(O(5n \lg{(5n)})\) using the big-oh notation.

Key Concepts

Factorial Function

The factorial function is a cornerstone in combinatorics, analysis, and number theory, symbolized by an exclamation point (!). For a positive integer, it's the product of all positive integers less than or equal to that number. Defined as \(n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1\), the factorial of a number exponentially increases as the number grows.

One may not only encounter natural numbers as input but also expressions such as \(5n\). In the exercise, \(f(n)\) involves computing the factorial of \(5n\), indicating the factorial function's flexibility in handling more complex expressions. This can be challenging to compute for large values of \(n\), leading us to utilize approximations for practical estimation of growth rates.

Logarithm Function

The logarithm function, meanwhile, increases much more slowly than the factorial. It tells you the power to which a number (the base) must be raised to get another number. It is often used in complexity analysis because it grows slower than polynomial functions, and is indicated as \(\lg(x)\) when using a base of 10.

The function appears in our exercise as \(\lg(5n)!\), wrapping the factorial function. When analyzing the growth of this combination, the properties of both functions come into play. The slow growth rate of the logarithm tempers the explosive increase of the factorial, but as we will see through Stirling’s approximation, the latter still dominates the growth behavior.

Stirling's Approximation

Sometimes computing the factorial function directly isn’t practical for large numbers. That’s where Stirling's approximation comes in. It provides a way to estimate the factorial of a large number without computing it exactly. The approximation is: \[n! \approx \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n\]

Applied to our exercise, we can estimate \[\lg{(5n)!}\] as \[\lg{\left(\sqrt{2 \pi (5n)} \left(\frac{5n}{e}\right)^{5n}\right)}\], breaking it down using properties of logarithms. This approximation is crucial because it simplifies our assessment of the function's growth and becomes particularly important when we are dealing only with the fastest growing part for big-oh notation.

Growth Rate Estimation

Estimating growth rates is fundamental in computer science to understand how algorithms perform as the size of the input data increases. The big-oh notation, represented as \(O(...)\), captures the upper limit of growth rates for functions. In our exercise, after applying logarithm to Stirling’s approximation and rewriting it, we observed that the term \(5n \lg{(5n)}\) is the dominating term in the context of growth rate.

This means that in terms of big-oh notation, we can express the growth of \(\lg{(5n)!}\) as \(O(5n \lg{(5n)})\). As the value of \(n\) becomes very large, the function \(f(n)\) will grow proportionally to \(n\) times the logarithm of \(n\), rather than the factorial of \(n\), simplifying analysis of the function's behavior for large input sizes.