Running time correct with Omega?
Don't guess, but look at the definition which tells you that in order for $f(n) = \Omega(g(n))$ to hold, it must be the case that $\lim_{n \to \infty} f(n)/g(n) &gt; 0$.

If I plug in $f(n)$ and $g(n)$ according to your description, I think I will get $\lim_{n \to \infty} f(n)/g(n) = 0$. You should check whether I made a mistake and draw the appropriate conclusions.