0

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?

Rao
  • 892
  • 1
  • 8
  • 20

2 Answers2

4

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
  • 23,769
  • 3
  • 56
  • 67
  • Is this not for finding small-oh? x__x Also, is there an alternative method that, say, uses only inequalities? – Rao Sep 13 '09 at 08:39
  • 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 Sep 13 '09 at 09:29
  • 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 Sep 13 '09 at 09:34
  • I guess it would be essentially trial and error, but it would be fairly simple to make good guesses with similar enough functions. – bobbymcr Sep 13 '09 at 10:12
3

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)

Community
  • 1
  • 1
Mitch Wheat
  • 295,962
  • 43
  • 465
  • 541