Big O if 2^n vs. 4^n

Question

I'm trying to figure out these two Big O's. Obviously the big O of 2^n is O(2^n), but I'm not sure if you can reduce 4^n. If so, I would do 4^n = (2^2)^n. Then we could distribute to make this 2^(2n), which I would reduce to O(2^n) since the constant in front of the n wouldn't matter.

Is this correct? Thank you.

Answer 1

Let's try to arrive at this for ourselves. Assume 4^n = O(2^n). Then there is some m and some c such that 4^n <= c*2^n for all n >= m. Then we have for all n >= m:

   (2*2)^n <= c*2^n
=> 2^n * 2^n <= c*2^n
=> c >= 2^n

So c can clearly not be constant, a contradiction.