Confused about big O of n^2 vs 2^n
This question already has an answer here:
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?
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 .
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.
链接地址: http://www.djcxy.com/p/6758.html