>What you're saying is theoretically true. In practice, very few people >run into the non-O(n) nature of lists, because the constant factor for >expansion is large enough and other operations tend to swamp the list >resize time. The dispatch time from Python-to-C alone is enough to mask plenty of time. C//