（另一种快速排序的分析方法）对随机化版本的快速排序算法，还有另一种性能分析方法，这一方法关注于每一次单独递归调用的期望运行时间，而不是比较的次数。
a.证明：给定一个大小为n的数组，任何特定元素被选为主元的概率为1/n，利用这一点来定义指示器随机变量Xi=I{第i小的元素被选为主元}，E[Xi]是什么？
b.设T(n)是一个表示快速排序在一个大小为n的数组上的运行时间的随机变量，试证明：
c.证明上述公式可重写为：
d.证明：
（提示：可以将该累加式分成两个部分，一部分是k=2,3...,
，另一部分是k=
,...,n-1。）
，另一部分是k=,...,n-1。） e.利用d中的公式给出的界证明：c中的公式的递归式有解%5D%3D%5CTheta(nlgn))
。（提示：使用代入法，证明对于某个正常数a和足够大的n，有%5D%5Cleq%20anlgn)
。）
