# Asymptotic analysis with factorial and exponential

I'm solving a complexity question where I have:

$$n!/2^n$$

The goal is to find an upper bound for this.

My idea is using the fact that: $$n! = O(n^n)$$ $$n!/2^n = O((n/2)^n) = O(n^n)$$

But is a correct upper bound, and if so is it the tightest upper bound that can be found? I know that n! is asymptotically larger than 2^n, but I'm struggling to do a tighter analysis.

• Use Stirling’s approximation. – Yuval Filmus May 4 '19 at 21:38

Stirling's approximation states that $$n! \sim \sqrt{2\pi n} (n/e)^n.$$ It follows that $$n!/2^n \sim \sqrt{2\pi n}(n/2e)^n = \Theta(\sqrt{n}(n/2e)^n).$$