3.3 The joy of O(1)

How long should it take for len to compute the length of the list? One way is to iterate through the list:

1. Initialize a counter to 0.
2. If the list is not empty, go to the first item and add one to the counter. Otherwise, return the value of the counter, which is 0.
3. Try going to the next item. If it is not present, we have reached the end and return the counter. Otherwise, go to the item and increment the counter.
4. Go back to the previous step and repeat until we are finished.

There is a computing time overhead in moving from item to item and incrementing the counter. Let’s call this C. If our list has n items, then

time to compute the length by this method ≤ C × n.

If your computer is faster than mine, your C might be smaller. C also depends on the implementation of lists and Python itself.

This algorithm is O(n): its time is proportional...