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?
Asked
Active
Viewed 3.3k times
14
Software Guy
- 3,190
- 4
- 21
- 21
-
3*"if the value of n is 3"* - well there's your problem. Big O is about **large values of n**. – jonrsharpe May 28 '17 at 21:03
4 Answers
17
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:
Abe
- 485
- 5
- 17
-
2
-
Best way to get a sense of this is to look at graph of `2^n` and `n^100` – Nagendra Rao Jul 28 '20 at 17:07
4
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.
Rafael Kallis
- 158
- 8
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.
giliev
- 2,938
- 4
- 27
- 47
2
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.
Chen Kinnrot
- 20,609
- 17
- 79
- 141