O(n^2), again, now in Windows Management Instrumentation
I have my own O(n^2) blow-up story.  Back in the day I wrote some Google AdWords analysis software in a functional language.  Being written in a functional language meant that using association lists (linked lists for key&#x2F;value) was very natural.  Anyway these were only used to load the analysis inputs which was written in an Excel spreadsheet (the customer insisted on this!), exported to a CSV and loaded into the software.  The spreadsheet was only perhaps 5 rows so, whatever.<p>One day I got a call from the customer that his analysis was taking 6 hours to run, for a program that should have finished in a fraction of a second.  It turned out the customer had tried to load a 30,000 row spreadsheet of input.  The program would on every loop iterate over the input association list, resulting in classic O(n^2) performance overall.<p>After changing all the places to use a hash table it again ran in sub-second, although the code was nowhere near as elegant.