Whats the dominant term in 2^n or n^2 for big O notation
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.
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.
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:
f(n) = o(g(n)) if and only if the limit f(n)/g(n) becomes zero as n goes to infinity.
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 | n^2 <= a | 2^n | for all n >= b , which is simple algebraic manipulation.
2 ^ n是占优势的，因为对于较大的n，它增长得更快。
链接地址: http://www.djcxy.com/p/40044.html上一篇: 算法的渐近行为和Big O比较