Explore BrainMass
Share

Explore BrainMass

    Definition of small O-notation

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

    See the attach file for problem. Please read R as R+

    Question :
    Prove that ! ( )
    n
    n ∈ο n by using the definition of the small o- notation.
    Definition: Let : N →R∪{0}, where

    N is the set of all non-negative integers:
    R is the set of all positive real numbers.
    f
    0 0
    o( f )={ g : N →R ∪{0}|∀c∈R,∃n ∈N :g(n) <cf (n),∀n ≥n }
    Solution
    The factorial of n, represented by n! is defined for integers n ≥ 0 as
    n! = 1 if n=0
    = n. (n-1)! if n>0
    First of all let us try and arrive at an intuitive solution. A weak upper bound on n! is n
    n
    , since
    each of the n terms in the factorial product is at most n. The o-notation is used to denote an upper
    bound that is NOT asymptotically tight.
    Hence, intuitively ! ( )
    n
    n ∈ο n
    Proof:
    To prove this we need to prove that the definition of o-notation holds.
    According to the definition of o-notation, we need to prove that for any positive constant c > 0,
    there exists a constant n0 >0 such that
    0 ≤ n! < c n
    n
    for all n ≥ n0 Equation (i)
    So it now boils down to showing that the inequalities hold and then we are done.
    (a) The first inequality (0 ≤ n!) follows from the definition of n! :
    • n! is always greater than 0.
    • Minimum value of n! is 1 which occurs when n=0.
    Hence n! ≥ 0 for all n ≥ 0.
    (b) To show the second inequality, we just need to look at the factorials carefully.
    Once again, let us start with the basic factorials: 0! = 1 and 1! = 1. So in order for these factorials
    to satisfy the inequality, it is obvious that c must be >1 [because 1 < c*1 iff c >1].
    For all other factorials, i.e. n ≥ 2, the inequality will hold for any c > 1. So, in order to
    summarize:
    The second inequality n! < c n
    n
    is true for n ≥ 2 for any c ≥1. This is in the same form as
    Equation (i).
    Therefore for all c ε R+, n0 = 2 satisfies Equation (i).
    Hence ! ( )
    n
    n ∈ο n is proved

    © BrainMass Inc. brainmass.com October 9, 2019, 3:37 pm ad1c9bdddf
    https://brainmass.com/computer-science/c/definition-small-notation-8631

    Attachments

    Solution Summary

    The definition of small o-notation is examined. The non-negative integers and positive real number functions are given.

    $2.19