The initial perl version sported a states collection implemented as an unordered list. I kept an array of states (it could have been a linked list, too) and whenever I encountered a newly visited state, I added it to the end of the array. To search for the existence of a state in the state collection, the list was scanned element by element.
Assuming a comparison and an assignment are O(1) operations (an assumption which would be kept for the rest of this chapter), then it can be seen that an insertion takes O(1) time while a lookup take O(n) time. Since we encounter many states, then we want the lookup to be as fast as possible. But in this case it is O(n).
O(n) is the worst possible lookup complexity for a collection, and as more states are collected, it will become worse and worse to lookup one in it. I became aware of this fact, as I noticed that the perl program ran very slowly. O(n) lookup is in most cases very unacceptable and you should avoid it whenever possible.