CODEWITHSUNDEEP
algorithmtime-complexitybig-ocomputer-scienceexponential
BinaryGamer
BinaryGamer

Reputation: 33

Is O(3^n) still written as O(2^n)?

I'm wondering if an algorithm with an exponential worst time complexity, should always have that stated as O(2^n). For example, if I had an algorithm that's operations triple for each addition to the input size, would I write it's time complexity as O(3^n), or would it still be classified as O(2^n).

Any formal explanation would be greatly appreciated.

Upvotes: 3

Views: 1648

Answers (2)

Jasmeet
Jasmeet

Reputation: 1460

3^n != O(2^n).

Let us assume that it were true. Then there exists constants c and n0 such that 3^n ≤ c * 2^n for all n ≥ n0.

The last requirement is equivalent to (3/2)^n ≤ c for all n ≥ n0.

However, (3/2)^n → ∞ as n → ∞, so (3/2)^n ≤ c cannot be true for all n ≥ n0 for any constant c.

Upvotes: 6

Paul Hankin
Paul Hankin

Reputation: 58339

No, O(2^n) and O(3^n) are different. If 3^n were O(2^n), there'd be a constant k such that 3^n <= k * 2^n for all large n. There's no such k because 3^n / 2^n is (3/2)^n which grows arbitrarily large.

Upvotes: 2

Related Questions