Granted, about twenty years passed before anyone had an array of >2^31 elements in Java and noticed this bug in binary search: http://googleresearch.blogspot.c

Granted, about twenty years passed before anyone had an array of >2^31 elements in Java and noticed this bug in binary search: http://googleresearch.blogspot.ca/2006/06/extra-extra-read-all-about-it-nearly.html http://googleresearch.blogspot.ca/2006/06/extra-extra-read-a... If people are using abstract data types and/or built-ins, in practice, presumably they can use a fixed int type for O(1) runtime and just update the data type every 20 years or so. On that note, has anyone actually created a 2^128 element array yet? I suspect such an array would be too large to represent in the memory of all the world's computers at the moment.