如果寻找的元素属于集合并且在任意索引位置的概率是相等的（换句话说，它被迭代器在任意位置找到的几率是相等的），那么这就是平均情况下顺序查找（如我们在第2章所述）。
也就是说，对于每个目标元素来说，你将需要寻找集合中大约一半的元素。最好情况即待查找的元素是集合中的第一个。算法在最坏和平均情况下都是线性增长的。如果你加倍集合的大小，那么查找的时间也大约会是两倍。
为了得到顺序查找的实际性能，我们构造了一个包含n个整数（范围为[1,n]）的有序集合。虽然这个集合是有序的，但是查找时并没有用到这个信息。我们将会进行100次试验；每一次试验我们执行1000次查找随机值t。我们抛弃最好和最坏的结果，然后对剩余的结果取平均值。表5-1是四个特定的p值，剩余98次的平均时间。注意当集合的大小加倍时，执行时间也大约加倍。你也需要看到，对每一种输入集合的大小来说，最后一列表示最坏情况的时间。
在最好情况下，集合的第一个元素就是需要的元素，这样仅仅需要花费O(1)常数时间。最坏的情况是寻找的元素不在集合中，在这种情况下，你需要检查集合中的所有元素，导致了O(n)的性能，平均情况下（如第2章所述，并且如表5-1所示），性能是O(n)。