Big-O notation

[Duncan Booth]

Roy Smith <roy at panix.com> wrote in news:roy-
92A049.08504216042003 at reader1.panix.com:

>  Imagine you've got a program which runs in O(N^2) 
> time.  If you could find a way to reduce it to O(N), for an input set of 
> just 10 items, you would have speeded it up by a factor of 10!  Compared 
> to upgrading your Python interpreter, you did 50-100 times better tuning 
> the algorithm.  Now try to consider the implications of going from 
> O(N^2) to O(N) with 25,000 input items!

I believe you are making some unreasonable assumptions here. Remember that 
if I have an algorithm that is O(N^2) that is really just a shorthand for 
saying that it will have a running time a*N^2 + b*N * c where a, b, and c 
are constants but for sufficiently large N only the N^2 term matters.

Now imagine that you have a program that runs in O(N^2) time and you have 
10 items. If a is 1 and b is 1000, the N^2 term doesn't start to dominate 
until you have at least 1000 items. If these are times in milliseconds, 
then your 10 item program would take ~10 seconds to run, but improving the 
algorithm from O(N^2) to O(N) (with the same value for b) would have no 
noticeable effect.

Yes, if you have 25,000 items then for my chosen values of a and b the O(N) 
algorithm is probably going to result in a significant speedup (unless it 
increases b by a factor of more than 26), but you can't just simplify this 
to say that O(N) is going to be better in all cases.

If you try to apply this to the real world you may find there are all 
manner of compromises to be made. The most obvious one is in sorting where 
a real implementation of an O(n log n) sort will adapt to using an O(n^2) 
sort on subsets of the data because it turns out that the dumb sorting 
techniques are faster until n gets quite large.

-- 
Duncan Booth                                             duncan at rcp.co.uk
int month(char *p){return(124864/((p[0]+p[1]-p[2]&0x1f)+1)%12)["\5\x8\3"
"\6\7\xb\1\x9\xa\2\0\4"];} // Who said my code was obscure?