Big O Notation Of Exponential Functions

Question

I have noticed that big-O of 1000n or 10n is the same thing as O(n), but big-O of 2^n and 3^n are different: O(2^n) and O(3^n), what I don't get is why can't we ignore the constants in this case (2 or 3) and whether there is any mathematical proof justifying this?

Answer 1

Because there is no constant value of k that satisfies the inequality 3^n <= k * 2^n for arbitrarily large n. Thus f(n) = 3^n is not a member of O(2^n).

See http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations.

Answer 2

Eventhough for the original asker this might not be of use anymore,
I think it can be approached in an easier way.

Basic defenition of O-notation: iff f(g) would be in O(g(n)),
then there exist a rational number c, for which it holds that f(g) = c * g(n), for n >= n0
(n0 being a number that you pick yourself)

Let's try to apply this for 3^n in O(2^n)
3^n = 2^n * c
3^n = 2^n * (3^n / 2^n)
3^n = 2^n * (3/2)^n
3^n = 2^n * 1.5^n

this means that c = 1.5^n which is not a rational number, but an exponential function on its own.

On the other hand, following the same for 3^n in O(2^n), we would get 2^n <= 3^n * (2/3)^n

This might seem like a conflict, until you realise that 0.75^n < 1 for all n > 0, which means that if you take any c > 1, it will be larger than 0.67^n from n = 0