Explore BrainMass

# Asymptotically tight bounds on lg(n!)

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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 ad1c9bdddf
https://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