Big-O notation
Duncan Booth
duncan at NOSPAMrcp.co.uk
Wed Apr 16 15:39:41 CEST 2003
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?
More information about the Python-list
mailing list