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.
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.
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.