CODEWITHSUNDEEP
algorithmcomplexity-theory
user1830621
user1830621

Reputation: 13

Prove 2^(n a) = O(2^n)?

How can I prove that 2^(n+a) is O(2^n)? The only thing I can think of is that n in 2^n is an arbitrary value, therefore n+a is just as arbitrary, so n+a = n. Alternatively, 2^(n+a) = 2^n * 2^a. 2^n is obviously O(2^n), and a exists as an arbitrary value in 2^a, so 2^a = 2^n = O(2^n). Is there a clearer/more formal way to prove this?

Upvotes: 1

Views: 152

Answers (3)

Joe K
Joe K

Reputation: 18424

For the formal definition of big-O, there must exist an M and n0 such that 2^(n+a) <= M*2^n for all n > n0.

If we choose M = 2^a, and n0 = 0, then we can see that 2^(n+a) = 2^a * 2^n = M*2^n, which is <= M*2^n for all n > n0. Therefore, 2^(n+a) is O(2^n)

Upvotes: 3

japreiss
japreiss

Reputation: 11251

In general, to prove that f(n) is O(g(n)), you must find a positive integer N such that for all n >= N, f(n) <= g(n).

Upvotes: 0

JJ Beck
JJ Beck

Reputation: 5283

See the definition of the big-O notation here. Think about whether you can find a constant M as in the definition.

Upvotes: 1

Related Questions