Big-O notation (was: Re: Python and Schools)
roy at panix.com
Wed Apr 16 00:58:44 CEST 2003
"Mike C. Fletcher" <mcfletch at rogers.com> wrote:
> You can have all sorts of fun learning how to combine and re-factor the
> equations to get a final big-O notation, but for the most part,
> practical coders can get away with recognising and avoiding O(N**X)
> where X > 1 situations.
Indeed. Lest people think this is of academic interest only, let me
describe a situation we had at my company recently.
We've got something which scans a directory (an O(N) process). It's
supposed to happen once every time the program is run. Somebody goofed
in coding, and moved it into the loop that happens once every input
file, not once per run. Now it's an O(N^2) process.
Nobody noticed it in testing because we only tested it with maybe 100
files. Then one of our customers ran it with 25,000 files (a perfectly
reasonable thing to do). Whoops :-)
More information about the Python-list