现在要设计一个支持n个电话的电话系统，n是一个非常大的数目，要求在最坏情况下，即n/2位用户同时呼叫另外n/2位用户时，这个系统也能够正确地处理数据。虽然这个系统不会由于过载而崩溃，但需要花费过高的代价构造这样的情况。而且，n/2位用户同时呼叫另外n/2位用户发生的概率极小。也许可以设计一个花费较小的系统在过载的情况下很少会（或者从不）崩溃。但是我们还是必须借助数学工具来计算这个概率问题。
对于一个n个样本的数据集合，我们用一个概率分布Pr表示样本的出现概率，单个样本的出现概率为0到1，所有样本的概率的和为1。如果Sn是n个样本的数据集合，那么：
如果t表示算法在单个样本的执行时间，那么在Sn上的平均运行时间是：
也就是说，在样本si的实际执行时间，t(si)将会与概率加权。如果Pr{si}=0，那么t(si)的实际值将不会影响程序的期望运行时间。我们用Tac(n)表示算法在Sn上的平均运行时间，那么Tac(n)的增长率表示算法在平均情况下的复杂度。
回忆一下，当我们描述时间或者工作量的增长率时，我们一直忽视了常数，所以我们认为顺序搜索n个元素的平均情况为：
探测（符合我们之前的假设），按照惯例，在符合这些假设的前提下，期望顺序搜索能够处理线性或者是n阶的元素。