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

Question

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

Accepted Answer

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)`.

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

Solution

Problem