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 at 13:10
  • 3
    $\begingroup$ The tight lower bound is $n! = \Omega(n!)$. $\endgroup$ Jul 6 at 13:29
  • $\begingroup$ @YuvalFilmus I don't feel like that's particularly helpful $\endgroup$
    – exfret
    Jul 9 at 15:03
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 at 18:33
  • $\begingroup$ You are right. I will change it to theta to be more precise. $\endgroup$
    – exfret
    Jul 9 at 23:09
  • $\begingroup$ No I was not aware of Stirling's formula, thanks. $\endgroup$ Jul 12 at 13:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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