Asymptotically tight bounds on lg(n!)
Obtain asymptotically tight bounds (Big-Oh and Big-Omega) on lg(n!) without using Stirling's approximation. Instead, evaluate these using the expansion of lg(n!) as a summation.
© BrainMass Inc. brainmass.com March 4, 2021, 7:29 pm ad1c9bdddfhttps://brainmass.com/computer-science/algorithms/asymptotically-tight-bounds-104286
Solution Preview
lg(n!) can be expanded as
lg(n!) = lg{n*(n-1)*(n-2)* ... *1}
= lg(n) + lg(n-1) + lg(n-2) + ... + lg(1)
Finding upper bound (Big-Oh) for lg(n!)
---------------------------------------------
lg(i) <= lg(n) , for each i such that i>=1 and i<=n
Hence we can also write -
lg(n!) <= lg(n) + lg(n) + lg(n) + ... + lg(n)
OR
lg(n!) <= n*lg(n)
which is true for n>0 ...
Solution Summary
The solution computes the Big-Oh and Big-Omega bounds in stepwise manner with sufficient explanations.
$2.49