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:
- Initialize a counter to 0.
- 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.
- 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.
- 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...