Why is $\log n = O(2^n)$?
As stated, $\log (n) = O (2^n)$ is trivially true. 

All that it says is that $\log n$, in the end, grows no faster than $2^n$. For $2^n$, you can substitute $n$, $\sqrt n$, indeed any root of $n$. 



However carelessly stated, I think this really refers to the following:


To represent a number of size $2^n$, you need $n$ bits.
So, to represent a number of size $n$, you need $\log n$ bits.


Bits are a measure of space.



I made heavy weather of this before, as I thought it was referring to the time it takes to calculate $2^n$. In case it is, I'll leave this in:

For $n$ a non-negative integer, and $f(n) = 2^n$

$$
f(n) = 
\begin{cases}
1 &amp;\text{for }\, n = 0 \\
(f (n \div 2))^2\times 2^{(n \mod 2)} &amp;\text{for}\; n \gt 0
\end{cases}$$

The implied algorithm is clearly $\Theta (log \, n)$. But this is time complexity. In space complexity, it is $\Theta(1)$. 




$\Theta (f)$ are the functions that, adapting the words of Wolfram
Mathworld, are no worse but also no better than $f$.
$O (f)$ are the functions that are no worse than $f$.