Whats the dominant term in 2^n or n^2 for big O notation

Question

I have been looking at Big O notation and have come across an operational count 2^n+n^2. I understand the practice of big O notation is to remove the constants and the low order terms, however I cant figure out which one to make O(n). I think it may be 2^n but have had no luck finding anything to suggest this.

Answer 1

Look at the growth factor over time. For the first eight values of n, O(n^2) works out to:

0, 1, 4, 9, 16, 25, 36, 49...

O(2^n) produces powers of two:

1, 2, 4, 8, 16, 32, 64, 128...

It should be fairly obvious which one is growing faster.

Note that the general rule applies even with different bases and exponents. O(1.1^n) may have initially lower work than O(n^10) for smaller n, but all exponential growth with an exponent greater than 1 will eventually outpace fixed exponent polynomial growth as n approaches infinity.

Answer 2

By L'Hopital's rule:

lim_{n -> infinity} (n^2 / 2^n )

= 1/log(2) lim_{n -> infinity} (2n / 2^n)

= 1/log(2)^2 lim_{n -> infinity} (2 / 2^n)

= 0

We have n^2 = o(2^n) which implies n^2 = O(2^n).

If this proof doesn't make sense: By definition, f(n) = O(g(n) if and only if f(n) is bounded within some constant multiple of g(n) after n grows past some constant. And a way to think of f(n) = o(g(n)) is that as n grows to infinity, g(n) will continue to outgrow f(n) faster. In other words:

1. f(n) = o(g(n)) if and only if the limit f(n)/g(n) becomes zero as n goes to infinity.

2. o(g(n) is a strictly stronger condition that f(n) = O(g(n)).

Alternatively, you just need to use the definition directly: Find some a and b such that n^2 <= a | 2^n | for all n >= b, which is simple algebraic manipulation.