Are the two difficulties O ((2n + 1)!) And O (n!) Equal?

Question

This may be a naive question, but I'm new to the concept of notation and complexity of Big-O and could not find an answer to this. I am dealing with a problem for which the algorithm is (2n + 1)! time checks the status. Can I say that the complexity of the problem is O (n!) Or the complexity of O ((2n + 1)!)?

Answer 1

Use Stirling Shift :

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 is no hope for O((2n + 1)!) be O(n!) : Exponential factors are worse. This is more like O((2n + 1)!) Is O((n!)^2) .

Answer 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 the function (2n + 1) !, that is, not in O (n!), Therefore O ((2n + 1)!) And O (n!) Are not the same.

(I agree with LaTeX's desire.)

Answer 3

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

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

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

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

(2n + 1)! it just goes twice as fast, so regardless of c it will always reach n !. Therefore, you cannot simplify n !.

Answer 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)!)