Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Give a big-O estimate of the product of the first n odd positive integers

  1. Jul 17, 2011 #1
    1. The problem statement, all variables and given/known data
    Give a big-O estimate of the product of the first n odd
    positive integers.

    2. Relevant equations
    Big-O notation:
    f(x) is O(g(x)) if there are constants C and k such that
    |f(x)| ≤ C|g(x)| whenever x > k.

    3. The attempt at a solution
    The product of the first n odd integers can be given by:
    [tex]P(n)=1\times 3\times 5\times 7\times...\times (2n-1)[/tex]
    For n > 0, no element in the above sequence will be greater than (2n-1). Thus:
    [tex]1\times 3\times 5\times 7\times...\times (2n-1)\leq (2n-1)\times (2n-1)...\times (2n-1)=(2n-1)^n[/tex]
    So:
    P(n) ≤ (2n-1)n whenever n > 0
    I could stop here and say that
    P(n) is O((2n-1)n)
    But to simplify I think I could consider that:
    P(n) ≤ (2n-1)n ≤ (2n)n
    Thus,
    P(n) is O((2n)n)

    Is this reasoning correct?

    Thank you in advance.
     
    Last edited: Jul 17, 2011
  2. jcsd
  3. Jul 17, 2011 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hi pc2-brazil! :smile:

    it's correct, but it's not very accurate, is it? :redface:

    do you know a big-O estimate for n! ? :wink:
     
  4. Jul 17, 2011 #3
    A big-O estimate for n! would be O(nn).
    I could say that, for n > 0,
    [tex]1\times 3\times 5\times 7...\times (2n-1)\leq 1\times 2\times 3\times 4\times...\times (2n-1)=(2n-1)!\leq (2n)!=2^n n![/tex]
    Thus, P(n) is O(2nn!). Since n! is O(nn), this estimate seems more accurate than the previous one (O(2nnn)).
     
  5. Jul 17, 2011 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Last edited by a moderator: Apr 26, 2017
  6. Jul 17, 2011 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    If En = product of the even numbers from 2 to 2n - 2, your product is (2n-1)!/En, and En = 2^(n-1) * (n-1)! Now apply Stirling's formula to both factorials. Note: if you want a true upper bound, rather than just an *estimate* you can use the fact that if St(n) is defined as
    sqrt(2pi)*n^(n + 1/2)*exp(-n), then we have St(n) <n! < St(n)*exp(1/(12n)), even if n is not large. You can use the upper bound on (2n-1)! in the numerator and the lower bound on (n-1)! in the denominator.

    RGV

    sqrt(2pi)*n
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook