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

[Roy Smith]

"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 :-)