1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Give a big-O estimate of the product of the first n odd positive integers
  1. Big-O estimate (Replies: 1)

Loading...