Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How do I prove $2^n = \Omega(n^2)$?

share|improve this question

closed as unclear what you're asking by O.L., Macavity, Michael Albanese, T. Bongers, Dominic Michaelis Oct 22 '13 at 5:14

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

Please write complete sentences. I have no idea what you are trying to say. I don't know what that $w$ is in $f(n)=w(2^n)$. –  Gerry Myerson Oct 23 '11 at 11:11
Do you mean that $n!$ is $\Omega(2^n)$? That at least is true. The rest makes no sense: $n!$ is not $o(a^n)$. It isn’t even $O(a^n)$. It is $\Omega(a^n)$; is that by any chance what you’re trying to show? –  Brian M. Scott Oct 23 '11 at 11:41
This can be generalized to $f(n) = \omega(c^n)$ for all constant $c$. –  Yuval Filmus Oct 23 '11 at 16:25

2 Answers 2

up vote 2 down vote accepted

If you look up the definition of little omega, one definition states that $f(n)=\omega(g(n))$ if \begin{align*} \lim_{n\to\infty}\frac{f(n)}{g(n)}=\infty. \end{align*}

Now, does $\lim_{n\to\infty}n!/2^n$ go to $\infty$?

EDIT: Sorry I mistyped the definion earlier, it is correct now.

share|improve this answer

If you're really lazy, you can always use Stirling's approximation, though it's an overkill unless you're trying to prove things like $n! = \omega(n^{(1-\epsilon)n})$.

share|improve this answer

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