Confused about big O of n^2 vs 2^n

Question

I read in a book that the following expression O(2^n + n^100) will be reduced to: O(2^n) when we drop the insignificant parts. I am confused because as per my understanding if the value of n is 3 then the part n^100 seems to have a higher count of executions. What am I missing?

Solution 1

Big O notation is asymptotic in nature, that means we consider the expression as n tends to infinity.

You are right that for n = 3, n^100 is greater than 2^n but once n > 1000, 2^n is always greater than n^100 so we can disregard n^100 in O(2^n + n^100) for n much greater than 1000.

For a formal mathematical description of Big O notation the wikipedia article does a good job

For a less mathematical description this answer also does a good job:

What is a plain English explanation of "Big O" notation?

Solution 2

The big O notation is used to describe asymptotic complexity. The word asymptotic plays a significant role. Asymptotic basically means that your n is not gonna be 3 or some other integer. You should think of n being infinitely large.

Even though n^100 grows faster in the beginning, there will be a point where 2^n will outgrow n^100.

Solution 3

You are missing the fact that O(n) is the asymptotic complexity. Speaking more strictly, you could calculate lim(2^n / n^100) when n -> infinity and you will see it equals to infinity, so it means that asymptotically 2^n grows faster than n^100.

Solution 4

When complexity is measured with n you should consider all possible values of n and not just 1 example. so in most cases, n is bigger than 100. this is why n^100 is insignificant.

View more solutions

Comments

[sepp2k]

"as n tends to some very large number." *to infinity

[Nagendra Rao]

Best way to get a sense of this is to look at graph of 2^n and n^100