Explore BrainMass

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

    Attachments

    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

    ADVERTISEMENT