I am currently learning complexity theory and wasn't able to find a tightest lower bound to BigOmega(n!), I am quite certain it isn't n^n and so wasn't able to reach to a tightest lower bound, can log(n)^n be the one, of course lose lower bounds are possible, but can you please help me understand the tightest lower bound of n!?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ Why you are not trying to use Stirling approximation formula? $\endgroup$– OmGJul 6, 2021 at 13:10
-
3$\begingroup$ The tight lower bound is $n! = \Omega(n!)$. $\endgroup$– Yuval FilmusJul 6, 2021 at 13:29
-
$\begingroup$ @YuvalFilmus I don't feel like that's particularly helpful $\endgroup$– exfretJul 9, 2021 at 15:03
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
You are indeed correct that it isn't $n^n$ (though this is good enough for most purposes). As OmG mentioned in the comments, there is a standard approximation formula called "Stirling's approximation formula" which gives the following asymptotic bound:
$$n!=\Theta\Big(\sqrt{n}\frac{n^n}{e^n}\Big)$$
-
$\begingroup$ Big O is an upper bound. OP was looking for a lower bound. $\endgroup$ Jul 9, 2021 at 18:33
-
$\begingroup$ You are right. I will change it to theta to be more precise. $\endgroup$– exfretJul 9, 2021 at 23:09
-
$\begingroup$ No I was not aware of Stirling's formula, thanks. $\endgroup$ Jul 12, 2021 at 13:27