Big O relation between $2^n$ and $2^{2n}$ I know that:

If $f(n) = O(g(n))$ , then there are constants $M$ and $x_0$ , such that 

$f(n) &lt;= M*g(n), \forall n &gt; n_0$

The other, plain English way of defining it is,

If $f(n)=O(g(n))$ then for large $n$ , $f(n)$ would grow as fast as $g(n)$.

I got confused when comparing $2^n$ with $2^{2n}$. Here , $f(n) = 2^n$ and $g(n) = 2^{2n}$. Clearly , $f(n)$ is smaller than $g(n)$ by a factor of $2^n$. So there will be constants $A$ and $x_0$ such that the first definition above is met.

However, for large $n$ , $2^{2n}$ would grow much faster than $2^n$, leaving $2^n$ far behind. That is $2^{2n}$  won't be an asymptotic/tight bound for $2^n$ .

So, is $2^n = O(2^{2n})$ or not? (or did I just create a confusing situation out of nothing)
The more strong estimate is correct:

$2^n = o(2^{2n})$

Just look at definition of the little-o. For any constant $c \gt 0$ you need to find a constant $n_0$, such that for all $n \ge n_0$ you get $2^n \le c \cdot 2^{2n}$. Apparently, the following inequality will give you this $n_0$:

$n_0 \ge ln(1 / c)$