http://www.nist.gov/dads/HTML/bigOnotation.html
and
http://en.wikipedia.org/wiki/Big_O_notation
may help.
It's really very simple once someone explains it. My understanding is that, for typical uses in terms of computing algorithms, it is typically used to represent "scaling" efficiency of algorithms.
O(n^2) is _fine_ for small values of n (usually data set size / number of items/records ), but quickly becomes a problem as n grows.
Here's an example from an app I'm currently working on. There's a function that runs in O(n^2) time, and I need to use it with large data sets. As it's not a superfast operation anyway, the result is it's just too slow for me to be able to use.
I have to options to fix it.
(a) find a way to improve it in a constant way, and improve it enough that for my data sets the completion time is OK. I then have to hope my data sets don't grow.
(b) Improve it so that the increase in run time grows more slowly as n increases.
Currently:
Num rows Completion time
1000 3.7s
2000 11s
3000 25s
4000 46s
100000 ???
Not cool for web document delivery ;) Note that the completion time is growing (roughly) in proportion to the square of number of rows:
1000**2 / 3.7 == 270270
2000**2 / 11 == 363636
3000**2 / 25 == 360000
4000**2 / 46 == 347826
I've been able to make some changes that allow the function to complete in O(n) time. Now (yeah, I know the row counts tested with are different):
4000 : 5s
8000 : 10s
20,000 : 24s
100,000: 131s
or:
4000/5 == 800
8000/10 == 800
20000/24 == 833
100000/131 == 763
make sense? The function used to process the data (n) times, meaning that it'd be procssing twice the data twice as many times when the data size was doubled. O(n^2). The revised function only processes the data once, and is able to complete in O(n) time.
The article comments on people being obsessed with improving algorihmic efficiency in terms of logical completion times  taking an O(n^2) algorithm to an O(n) one, for example. While I agree there are times that you can say "instead, I'm better off getting a 100fold linear improvement in speed on my O(n^2) algorithm, that'll be good enough for the data set size I expect to use" there are also times when you need to say "O(n^2) is not OK; we need large data sets and I don't think we'll be getting the tenmillionfold linear speed improvement we'd need."
Both have value.
