Factorials

The notation n! is defined for integers n ≥ 0 as

( ||{ → 1 if n = 0 n! = (1.2.23) ||( → n ⋅(n - 1)! if n > 0

And the a binary logarithmic of factorial n can be tight bounded into n ⋅ lg n,

lg(n!) = lg (1) +lg(2)+ ...+ lg(n-)+ lg (n+ 1)+ ...+ lg lg(n) n 2 2 ≥ ∑ lg(k) k=n+1 2n ≥ ∑ lg(n-) k=n+1 2 n 2 n = --⋅lg (-) 2 2 = Ω(n ⋅lg(n)) n n lg(n!) = lg (1) +lg(2)+ ...+ lg(--)+ lg (-+ 1)+ ...+ lg lg(n) ∑n 2 2 = lg(k) k=1 ∑n ≤ lg(n) k=1 = n⋅lg(n) = O(n ⋅lg(n)) lg(n!) = Θ(n ⋅lg(n)) (1.2.24)

Stirling's Approximation

A loose upper bound on the factorial function is n! ≤ nⁿ, which leads to this Stirling’s Approximation:

√----- n n 1 lgn! = 2π ⋅n⋅(e-) ⋅(1+ Θ(n-)) (1.2.25)