1

Possible Duplicate:
Plain English explanation of Big O

I need to figure out O(n) of the following:

f(n) = 10n^2 + 10n + 20

All I can come up with is 50, and I am just too embarrassed to state how I came up with that.

Can someone explain what it means and how I should calculate it for f(n) above?

Community
  • 1
  • 1
lovetolearn
  • 93
  • 1
  • 4
  • 11
  • 3
    You are miunsrstanding the nature of the question when asked what is O(n) - have a read up on Big O notation. http://en.wikipedia.org/wiki/Big_O_notation – Andrew Nov 09 '11 at 23:43
  • The problem probably lies in that `10n2` should be `10n^2`. – corsiKa Nov 09 '11 at 23:44
  • @glowcoder - I don't think that's the whole problem. – Don Roby Nov 09 '11 at 23:45
  • 2
    The question is _far_ too broad in scope: you are asking us to teach you something which should be learned over a period of several lectures and assignments. Perhaps go back to the teacher who set you the homework -- did he/she not also spend four hours explaining algorithmic complexity analysis in great detail beforehand? – Lightness Races in Orbit Nov 09 '11 at 23:49
  • @TomalakGeret'kal He did which is why I am not going to him. – lovetolearn Nov 10 '11 at 00:05
  • @Java: Time for a new school! Or perhaps just begin with a book. – Lightness Races in Orbit Nov 10 '11 at 00:05
  • @TomalakGeret'kal I was joking, someone edited my question to say I have this homework, its not homework, i am going through some lecture slides for my lecture on Monday and one of the questions is this. Could not understand it so thought i would ask here. – lovetolearn Nov 10 '11 at 00:10
  • @Java: Why not wait until the professor explains it to you in the lecture? Rather than asking us to attempt to kludge out the entire topic in text? – Lightness Races in Orbit Nov 10 '11 at 00:14
  • @yoda: Please don't make assumptions like that. – Lightness Races in Orbit Nov 10 '11 at 00:15
  • @TomalakGeret'kal `f(n)=something, then O(n)=?` (see first rev) sounds very much like a copy-paste from an assignment. I merely improved the bad shape the post came in. Also, I don't understand how that word would change the meaning of the post or the answer provided... – abcd Nov 10 '11 at 00:20
  • 1
    @yoda: A problem that is designed to be posed as a homework assignment isn't necessarily always solved _as_ a homework assignment ;) And the word "homework" has _significant_ connotations in the sorts of answers that result, on SO, due to anti-spoonfeeding policy. – Lightness Races in Orbit Nov 10 '11 at 00:23

1 Answers1

5

Big-O notation is to do with complexity analysis. A function is O(g(n)) if (for all except some n values) it is upper-bounded by some constant multiple of g(n) as n tends to infinity. More formally:

f(n) is in O(g(n)) iff there exist constants n0 and c such that for all n >= n0, f(n) <= c.g(n)

In this case, f(n) = 10n^2 + 10n + 20, so f(n) is in O(n^2), O(n^3), O(n^4), etc. The tightest upper bound is O(n^2).

In layman's terms, what this means is that f(n) grows no worse than quadratically as n tends to infinity.

There's a corresponding Big-Omega notation which can be used to lower-bound functions in a similar manner. In this case, f(n) is also Omega(n^2): that is, it grows no better than quadratically as n tends to infinity.

Finally, there's a Big-Theta notation which combines the two, i.e. iff f(n) is in O(g(n)) and f(n) is in Omega(g(n)) then f(n) is in Theta(g(n)). In this case, f(n) is in Theta(n^2): that is, it grows exactly quadratically as n tends to infinity.

--> The point of all this is that as n gets big, the linear (10n) and constant (20) terms become essentially irrelevant, as the value of the function is far more affected by the quadratic term. <--

Stuart Golodetz
  • 20,238
  • 4
  • 51
  • 80