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?
views:
84answers:
2
+3
A:
Please see:
Big O Notation Homework--Code Fragment Algorithm Analysis?
Big O, how do you calculate/approximate it?
Can someone please explain the difference between Big-O and Little-O Notation?
Big-O for Eight Year Olds? (not meant to be insulting)
Mitch Wheat
2009-09-13 08:04:21
+4
A:
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).
bobbymcr
2009-09-13 08:12:49
Is this not for finding small-oh? x__xAlso, is there an alternative method that, say, uses only inequalities?
Rao
2009-09-13 08:39:46
Little o is different; that's where lim (n->inf.) f(n)/g(n) = 0, meaning g(n) grows faster than f(n) (e.g. n is o(n^2) since n^2 grows faster than n). You could use inequalities to show that f(n) <= M*g(n) for some real number M in order to prove that f(n) is O(g(n)).
bobbymcr
2009-09-13 09:29:57
Ah ok, ok. And in the inequality method, we can only proceed by trial and error to get the constants, since we need to get proper values for both M AND n-knot?
Rao
2009-09-13 09:34:27
I guess it would be essentially trial and error, but it would be fairly simple to make good guesses with similar enough functions.
bobbymcr
2009-09-13 10:12:40