Complexity notation (Omega) consequence 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..
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)$.
This seems to be true for non-negative functions, and generally pretty false.

Suppose for all $n\geq N$, we have a constant $c&gt;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} &amp;\leq 2^{|f(n)|} \\
2^cn &amp;\leq 2^{|f(n)|} \\
c'n &amp;\leq 2^{f(n)} \\
c'n &amp;\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.