Two candies

[Terry Jones]

>>>>> "Raymond" == Raymond Hettinger <python at rcn.com> writes:
Raymond> * in most apps (except for sparse arrays), the initialization time
Raymond> for an array is dominated by the time spent actually doing
Raymond> something useful with the array (iow, this is an odd place to be
Raymond> optimizing)

This brings to mind an old algorithms chestnut (exercise 2.12 in the 1st
edition of Aho, Hopcroft & Ullman [1]):

If the implementation of an algorithm uses (for simplicity's sake) a square
array to represent its data, why are _all_ such algorithms not necessarily
O(n^2) due simply to the initialization requirement (supposing a model of
computation that counts assignments)?

Terry

[1] http://www.amazon.com/Analysis-Algorithms-Addison-Wesley-Information-Processing/dp/0201000296