Complexity notation (Omega) consequence

Question

In my algorithms class, the professor told us that the following holds: $$ \text{If } f(n) = \Omega(\log_2 n) \implies 2^{f(n)} = \Omega(n)$$

But is this always true ? I couldn't come up with a counter example, but this looks a bit sloppy to me..

Answer 1

This seems to be true for non-negative functions, and generally pretty false.

Suppose for all $n\geq N$, we have a constant $c>0$ such that $c\log n \leq |f(n)|$. Since $2^x$ is an increasing function we can apply it across the inequality and preserve the validity of the statement:

\begin{align*} 2^{c\log n} &\leq 2^{|f(n)|} \\ 2^cn &\leq 2^{|f(n)|} \\ c'n &\leq 2^{f(n)} \\ c'n &\leq \left|2^{f(n)}\right| \end{align*}

The next-to-last step requires a bit of justification. It of course holds only if $f(n)$ is non-negative.

For a counterexample in the general case, note that if $f(n)=-\log n$ then $f(n)\in \Omega(\log n)$ but $2^{-\log n} = 1/n$, so it cannot be asymptotically bounded below by any increasing function; $n$ in particular.

Answer 2

It's not just sloppy, but downright false. Please tell your professor that he/she is wrong.

Counter-example:

Let $f(n) = \frac12 \log_2(n)$. As $n \to \infty$, clearly $f(n) \in Ω(\log_2(n))$ but $2^{f(n)} \in o(n)$.