why is it a linear time to traverse a list?

You are totally right. If someone says that traversing a list if O(n), it is based on the assumption that you can get from one element to the next in constant time. If you change these assumptions, you may get a different time complexity.

When people state a time complexity for an algorithm and use it for discussing executions on real computers, the following fact is usually glossed over:

On a real physical computer, the number of different possible inputs is always finite, so a computer actually is a finite state machine (rather than a Turing Machine), and every algorithm has complexity O(1), strictly speaking (with a possibly rather large constant factor!). But we extrapolate this finite state machine to reason about its behaviour as if it weren’t finite.

In your example, the finite number of possible inputs for the list traversal algorithm is (in reality) bounded by the word length of the CPU (e.g. 64 bit), and you cannot have lists of length 2^100 (with the usual pointer-based algorithm). So strictly speaking, the complexity for traversing a list on a 64-bit CPU is O(1), but it behaves like O(n) within the range of possible inputs. The extrapolation breaks down for inputs outside of that range. That’s the case for all algorithms that run on a real physical computer.

CLICK HERE to find out more related problems solutions.

Leave a Comment

Your email address will not be published.

Scroll to Top