CODEWITHSUNDEEP
algorithmtime-complexitybig-o
thenac
thenac

Reputation: 305

What is the correct time complexity for n factorial time funcion?

I am very new to this topic and I am trying to grasp everything related to the asymptotic notations. I want to ask for your opinion on the following question:

If we have, for an algorithm, that T(n)=n!, then we can say for its time complexity that:

1 x 1 x 1 ... x1 <= n! <= n x n x n ... x n

This relation means that n! = O(n^n) and n! = Ω(1). However, can't we do better? We want the big-oh to be as close as we can to the function T(n). If we do the following:

n! <= 1 x 2 x 3 x 4 ... x n x n

That is, for the second to last element, we replace (n-1) with n. Now isnt this relation true? So isn't it true that n! = O(1 x 2 ... x n x n)? Something similar can be said for the lower bound Ω.

I am not sure if there is an error in my though process so I would really appreciate your input. Thanks in advance.

Upvotes: 2

Views: 2562

Answers (1)

Stef
Stef

Reputation: 15525

The mathematical statement n! = O(1 x 2 ... x n x n) is true. But also not terribly helpful nor enlightening. In what situations do you want to write n! = O(...)?

Either you are satisfied with n! = n!, and you don't need to write n! = O(1 x 2 ... x n x n). Or you are not satisfied with n! = n!; you want something that explains better exactly how large is n!; then you shouldn't be satisfied with n! = O(1 x 2 ... x n x n) either, as it is not any easier to understand.

Personally, I am satisfied with polynomials, like n^2. I am satisfied with exponentials, like 2^n. I am also somewhat satisfied with n^n, because I know n^n = 2^(n log n), and I also know I can't hope to find a better expression for n^n.

But I am not satisfied with n!. I would like to be able to compare it to exponentials.

Here are two comparisons:

n! < n^n
2^n < n!

The first one is obtained by upperbounding every factor by n in the product; the second one is obtained by lowerbounding every factor by 2 in the product.

That's already pretty good; it tells us that n! is somewhere between the exponential 2^n and the superexponential n^n.

But you can easily tell that the upperbound n^n is too high; for instance, you can find the following tighter bounds quite easily:

n! < n^(n-1)
n! < 2 * n^(n-2)
n! < 6 * n^(n-3)

Note that n^(n-3) is a lot smaller than n^n when n is big! This is slightly better, but still not satisfying.

You could go even further, and notice that half the factors are smaller than n/2, thus:

n! < (n/2)^(n/2) * n^(n/2) = (1/2)^(n/2) * n^n = (n / sqrt(2))^n =~ (0.7 n)^n

This is a slightly tighter upper bound! But can we do even better? I am still not satisfied.

If you are not satisfied either, I encourage you to read: https://en.wikipedia.org/wiki/Stirling%27s_approximation

Upvotes: 3

Related Questions