（比较排序的概率下界）在这一问题中，我们将证明对于给定的n个互异的输入元素，任何确定或随机的比较排序算法，其概率运行时间都有下界)
。首先来分析一下确定的比较排序算法A，其决策树为TA。假设A的输入的每一种排列情况都是等可能的。
a.假设TA的每个叶节点都标有给定的随机输入情况下到达该节点的概率。证明：恰有n!个叶节点标有1/n!，其他的叶节点标记为0。
b.定义D(T)表示一棵决策树T的外部路径长度，即D(T)是T的所有叶节点深度的和。假设T为一棵有k>1个叶节点的决策树，LT和RT分别是T的左子树和右子树。证明： D(T)=D(LT)+D(RT)+k。
c.定义d(k)为所有具有k>1个叶节点的决策树T的最小D(T)值。证明：%3Dmin_%7B1%5Cleq%20i%5Cleq%20k-1%7D%20%7Bd(i)%2Bd(k-i)%2Bk%7D)
。（提示：考虑一棵能够取得该最小值的，有k个叶节点的决策树T。设i0是LT中的叶节点数，k-i0是RT中的叶节点数。）
d.证明：d对于给定的k(k>1)和)
，函数ilgi+(k-i)lg(k-i)在i=k/2处取得最小值，并有结论%3D%5COmega(klgk))
。
e.证明：%3D%5COmega(n!lg(n!)))
，并得出在平均情况下，排序n个元素的代价为这一结论。
现在来考虑一个随机化的比较排序B。通过引入两种节点，我们可以将决策树模型扩展来处理随机化的情况。这两种节点是：普通的比较节点和“随机化”节点”。随机化节点刻画了算法B中所做形如RANDOM(1,r)的随机选择情况。该类节点有r个子节点，在算法执行过程中，每一个子节点等概率的被选择。
f.证明：对任何随机化比较排序算法B，总存在一个确定的比较排序算法A，其期望的比较次数不多于B的比较次数。
