Two candies

Terry Jones terry at
Thu Jan 3 02:06:56 CET 2008

>>>>> "Raymond" == Raymond Hettinger <python at> 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)?



More information about the Python-list mailing list