Fun stuff. My favorite example goes a long way back. The string garbage collection in Applesoft BASIC (Microsoft BASIC for the Apple II, introduced in 1977) ha

Fun stuff. My favorite example goes a long way back. The string garbage collection in Applesoft BASIC (Microsoft BASIC for the Apple II, introduced in 1977) had a loop that was written backwards. The result worked correctly, but it was accidentally quadratic. Variables were stored low in memory. A string variable held a pointer to its value, which was stored in high memory. When high memory filled up, GC ran on the string values, pushing the ones that were still used up to the top of memory. The main loop for this GC routine should have run from the top of string space to the bottom, copying each string value that was still used to its final location higher in memory. But, alas, it ran from the bottom of string space to the top, so each iteration copied up all used string values that had been found so far. Thus, if there were n used string values, the GC routine would do O(n^2) copy operations, instead of the O(n) copies that the correctly written routine would have done. So code like the following -- with K set to some appropriate value -- would, at some point, pause for a long time indeed. 10 DIM A$(K): REM STRING ARRAY; K SHOULD BE A LARGE-ISH NUMBER 20 FOR I = 0 TO K 30 A$(I) = "X": REM EVENTUALLY UNUSED VALUE; GC WILL DELETE 40 A$(I) = "Y": REM USED VALUE 50 NEXT I By "a long time" I mean rather more than an hour (maybe -- my memory grows dim).