CODEWITHSUNDEEP
algorithm
fYre
fYre

Reputation: 1270

Big O Notation Of Exponential Functions

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?

Upvotes: 19

Views: 47536

Answers (3)

Carlos Villaseñor
Carlos Villaseñor

Reputation: 11

to campare two complexities, f(n) and g(n) you applied the limit: lim_{n->\inf} f(n)/g(n) and you have three posible answers:

1) lim_{n->\inf} f(n)/g(n) = 0; this imply that f(n) ∈ O(g(n)) and g(n) ∉ O(f(n))

2) lim_{n->\inf} f(n)/g(n) = +/- inf; this imply that f(n) ∉ O(g(n)) and g(n) ∈ O(f(n))

3) lim_{n->\inf} f(n)/g(n) ∈ Real number; this imply that f(n) ∈ O(g(n)) and g(n) ∈ O(f(n))

Then to demostrade 2^n ∈ O(3^n) you operate like this

lim_{n->\inf} 2^n/3^n = lim_{n->\inf} (2/3)^n = 0

And is demostrated, and we also demostraded 3^n ∉ O(2^n), and is easy to see that 2/3 < 1 this make the limit to converge to 0 then the result of the limit depends of the constants, I mean lim_{n->inf} a^n = 0 if 0 < a < 1 and lim_{n->inf} a^n = inf if a > 1;

For a better understanding check: Introduction to Algorithms, Third Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein

I'm professor of algorithms, I hope it helped you. Take care.

Upvotes: 1

Work of Artiz
Work of Artiz

Reputation: 1090

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

Upvotes: 4

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272517

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.

Upvotes: 20

Related Questions