Big-O notation (was: Re: Python and Schools)

Roy Smith roy at
Wed Apr 16 00:58:44 CEST 2003

"Mike C. Fletcher" <mcfletch at> 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 mailing list