
# 
##  
**Stirling's approximation** is a mathematical formula used to estimate a factorial of a large number. It is named after the mathematician James Stirling.
Stirling's approximation is used in many engineering fields, including probability theory, statistical mechanics, mathematics, and computer science (CS).  

## Formula
The formula is given as follows:
$n! ≈ \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$

where, 
- $n$ is a significant positive integer
- $e$ is the mathematical constant approximately equal to $2.71828$
- $π$ is the mathematical constant approximately equal to $3.14159$.

This formula estimates $n!$ and becomes more accurate as $n$ gets larger.

## Application of Stirling's approximation in CS

Apart from mathematics and engineering. Stirling's approximation is used in computer science as well. It is generally used in the complexity analysis of an algorithm. The factorial function is a commonly encountered mathematical operation in many algorithms, and calculating the exact value of $n$ can be computationally expensive for large values of $n$.

With the help of Stirling's 
approximation formula, we can estimate the value of $n!$ without having to calculate the exact value. This can significantly reduce the algorithm's computational complexity. 

Let's look at an example.

## Example
Let's solve the $n!$ by a conventional method, which is:

$n! = n * (n-1) * (n-2) * (n-3) ..... 3 * 2 * 1$ 

The code for this approach is as follows:

def factorial(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

print(factorial(100))

Here, `factorial(n)` denotes the factorial of `n`. The time complexity of this algorithm is dominated by the time required to compute factorials, which is $O(n)$ for each factorial. 

Now let's see how Stirling's approximation approach can help us in exact approximation. Using Stirling's approximation, we can estimate the factorial of $n$ as:

$\mathrm{factorial}(n) \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$

Let's see the code to implement Stirling's approximation:


import math

def factorial_stirling(n):
    return math.sqrt(2 * math.pi * n) * ((n / math.e) ** n)

n = 100
approximation = factorial_stirling(n)
print(approximation)

Since the time complexity for calculating $n^n$ is $O(log n)$. So, the total time complexity for Stirling's approximation will be $O(log n)$.

Which is a more accurate estimate than the $O(n)$ estimate obtained by assuming that the factorials are computed exactly.


What is Stirling's approximation?

Stirling's approximation provides an efficient method for estimating factorials of large numbers, reducing computational complexity significantly.

What is Stirling's approximation?

Formula

Application of Stirling’s approximation in CS

Example