Big O notation: O((n-1)!) or O(n!) for T((n-1)!)?

Question

I have an algorithm that I have analysed to have a time complexity of (n-1)!.

To put this in big-O notation, would I write O((n-1)!) or O(n!)?

Answer 1

Let's have a look:

limn → ∞ n!/(n-1)! = limn → ∞ n = ∞

Thus (see the definition) (n-1)! is in o(n!) (little-o).

So if your algorithm complexity is in O((n-1)!), it is also in O(n!), so it is not wrong to write O(n!) instead of O((n-1)!), but O((n-1)!) is a tighter bound, so you should use this one.

It is basically the same as writing π ≤ 22/7 or π ≤ 4. Both is right, but π ≤ 22/7 is closer.

Answer 2

It should be O((n-1)!).

O(n!) is actually O(n⋅(n-1)!)