So here is a tricky problem that I have been stuck on for a while:
$$f(n) = n^3 \\ g(n) = 2^{n}$$
Prove that $$f(n) \notin \Omega (g(n))$$
So we can break out the negation of the definition of Omega:
$$\forall c, n_{0} \in \mathbb{R}^{+}, \exists n \in \mathbb{N}, n\geq n_{0} \wedge f(n) < c*g(n)$$
At this point, I think its best to focus on that second part. Proving $n\geq n_{0}$ will be pretty simple. The hard part, is proving that $n^3 < c*2^n$. I have tried taking $\log_2$ of each side, but that doesn't seem to lead to anything.
Please let me know if you have any advice for how to get started on solving this, and if you have any tips for solving these types of negations in general. I'm sure there is no 'formula' or 'step by step guide' to always getting these right, but any advice will be helpful!
Let $f(n) = n^3$, and $g(n) = 2^n$.
$$\lim_{n\to\infty}\dfrac{f(n)}{g(n)} = \lim_{n\to\infty}\dfrac{n^3}{2^n}$$
Because $f(\infty) = \infty$, and $g(\infty) = \infty$, apply L'Hopital's rule:
$$\lim_{n\to\infty}\dfrac{n^3}{2^n} = \lim_{n\to\infty}\dfrac{3n^2}{2^n\cdot\ln 2} = \lim_{n\to\infty}\dfrac{6n}{2^n\cdot\ln^22} = \lim_{n\to\infty}\dfrac{6}{2^n\cdot\ln^32} = 0.$$
Since $\displaystyle\lim_{n\to\infty}\frac{f(n)}{g(n)} = 0$, $f(n)\not\in\Omega\left(g(n)\right)$.