0
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Why you are not trying to use Stirling approximation formula? $\endgroup$
    – OmG
    Jul 6, 2021 at 13:10
  • 3
    $\begingroup$ The tight lower bound is $n! = \Omega(n!)$. $\endgroup$ Jul 6, 2021 at 13:29
  • $\begingroup$ @YuvalFilmus I don't feel like that's particularly helpful $\endgroup$
    – exfret
    Jul 9, 2021 at 15:03

1 Answer 1

3
$\begingroup$

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)$$

$\endgroup$
3
  • $\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$
    – exfret
    Jul 9, 2021 at 23:09
  • $\begingroup$ No I was not aware of Stirling's formula, thanks. $\endgroup$ Jul 12, 2021 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.