What is the proper method to go about finding the order of growth for this function?
-
06-07-2019 - |
Question
2^n + 6n^2 + 3n
I guess it's just O(2^n), using the highest order term, but what is the formal approach to go about proving this?
Solution
You can prove that 2^n + n^2 + n = O(2^n)
by using limits at infinity. Specifically, f(n)
is O(g(n))
if lim (n->inf.) f(n)/g(n)
is finite.
lim (n->inf.) ((2^n + n^2 + n) / 2^n)
Since you have inf/inf, an indeterminate form, you can use L'Hopital's rule and differentiate the numerator and the denominator until you get something you can work with:
lim (n->inf.) ((ln(2)*2^n + 2n + 1) / (ln(2)*2^n))
lim (n->inf.) ((ln(2)*ln(2)*2^n + 2) / (ln(2)*ln(2)*2^n))
lim (n->inf.) ((ln(2)*ln(2)*ln(2)*2^n) / (ln(2)*ln(2)*ln(2)*2^n))
The limit is 1, so 2^n + n^2 + n
is indeed O(2^n)
.
OTHER TIPS
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow