CODEWITHSUNDEEP
algorithmmathbig-o
follmer
follmer

Reputation: 1078

Big O if 2^n vs. 4^n

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.

Upvotes: 4

Views: 22206

Answers (2)

Niklas B.
Niklas B.

Reputation: 95338

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.

Upvotes: 22

Buddy
Buddy

Reputation: 11038

From the Wikipedia on Big O:

On the other hand, exponentials with different bases are not of the same order. For example, 2^n and 3^n are not of the same order.

Upvotes: 9

Related Questions