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

Question

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.

Answer 1

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.