Are the two complexities O((2n + 1)!) and O(n!) eq

问题:

This may be a naive question but I am new to the concept of Big-O notation and complexity and could not found any answer for this. I am dealing with a problem for which the algorithm (2n + 1)! times check a condition. Can I say that the complexity of the problem is O(n!) or the complexity is O((2n + 1)!)?

回答1:

Use Stirling's approximation:

n! ~ (n / e)^n * sqrt(2 * pi * n)

Then

(2n + 1)! ~ ((2n + 1) / e)^(2n + 1) * sqrt(2 * pi * (2n + 1))
          >= (2n / e)^(2n) * sqrt(2 * pi * 2n)
          = 2^2n * (n / e)^(2n) * sqrt(2) * sqrt(2 * pi * n)
          = sqrt(2) * (2^n)^2 * ((n / e)^n)^2 * sqrt(2 * pi * n)              

And now it's pretty clear why there's no hope of O((2n + 1)!) being O(n!): the exponential factors are way worse. It's more like O((2n + 1)!) is O((n!)^2).

回答2:

Let (N,c) be any ordered pair of positive constants. Let n be any integer such that n>N and n>c.

Then (2n+1)! > (2n+1)*n! > cn!

Thus for any pair of positive constants (N,c) there exists n>N such that (2n+1)! > cn!, so (2n+1)! is not O(n!).

O((2n+1)!) contains a function, (2n+1)!, that is not in O(n!), so O((2n+1)!) and O(n!) are not the same.

(I concur in wanting LaTeX.)

回答3:

Here is the definition: https://en.wikipedia.org/wiki/Big_O_notation . So we need to check whether there exists a constant c, and n0 such that:

(2n+1)! < cn! for n > n0

Intuitively, from observing how (2n+1)! and n! behave:

http://www.wolframalpha.com/input/?i=n!+%3E%282n+%2B1%29!

(2n+1)! just goes two times faster, so regardless of "c" it will always reach n!. So you can't simplify to n!.

回答4:

(2n+1)! = n!(n+1)...(2n+1)

O((2n+1)!) = O(n!)O((n+1)...(2n+1))

==>

O(1) = o((n+1)...(2n+1))

O(n!) = o((2n+1)!)