QuickSort()関数が最初に呼び出されたときの比較

        lower<=upper&&data[lower]<=div
        lower<=upper&&data[upper]>div

の実行回数は、

回である。そして、再帰呼び出しにより、 $\alpha$ 個と $\beta$ 個の場合のQuickSort()が呼び出されることになる。

個の時のトータルの比較回数を

として、これらの関係は、

$\displaystyle a_N=N+1+a_\alpha+a_\beta$

(1)

となる。もちろん、 $\alpha$ と $\beta$ は、

～

の値を取りうる。そして、 sort[]に格納されている値がランダムであれば、同じ確率で

～

の値をとる。さらに、 $\alpha$ と $\beta$ の和は

になることはクイックソートのアルゴリズムから自明である。したがって、

の期待値は、

$\displaystyle a_N$	$\displaystyle =N+1+\frac{1}{N-1}\left(a_1+a_2+a_3+\cdots+a_{N-1} +a_{N-1}+a_{N-2}+a_{N-3}+\cdots+a_1\right)$
	$\displaystyle =N+1+\frac{2}{N-1}\sum_{k=1}^{N-1}a_k$	(2)

となる。この漸化式から、

を求めることになるが、計算は結構大変である。まず、式(2)を

$\displaystyle (N-1)a_N=(N+1)(N-1)+2\sum_{k=1}^{N-1}a_k$

と変形しておく。つぎに、この式の

を

にした場合の式

$\displaystyle (N-2)a_{N-1}=N(N-2)+2\sum_{k=1}^{N-2}a_k$

を利用する。式(3)から式(4)の辺々を差し引いて整理すると、

$\displaystyle (N-1)a_N-(N-2)a_{N-1}$

$\displaystyle =(N+1)(N-1)-N(N-2)+2a_{N-1}$

(5)

となる。さらに、整理を進めると

$\displaystyle (N-1)a_N-Na_{N-1}$

$\displaystyle =2N-1$

(6)

となる。両辺を、

で割ると、

$\displaystyle \frac{a_N}{N}-\frac{a_{N-1}}{N-1}$	$\displaystyle =\frac{2N-1}{(N-1)N}$
	$\displaystyle =\frac{1}{N}+\frac{1}{N-1}$	(7)

となる。ここで、

を

と置くと、

$\displaystyle b_N-b_{N-1}=\frac{1}{N}+\frac{1}{N-1}$

(8)

となり、階差数列を用いて容易に計算できる。すなわち、

$\displaystyle b_N=b_2+\sum_{k=3}^N\left(\frac{1}{k}+\frac{1}{k-1}\right)$

(9)

である。

より、

となるので、

$\displaystyle b_N$	$\displaystyle =\frac{3}{2}+\sum_{k=3}^N\frac{1}{k}+\sum_{k=3}^N\frac{1}{k-1}$
	$\displaystyle =\frac{3}{2}+\left(\sum_{k=1}^N\frac{1}{k}-1-\frac{1}{2}\right)+ \left(\sum_{k=1}^N\frac{1}{k}-1-\frac{1}{N}\right)$
	$\displaystyle =-\frac{3}{2}-\frac{1}{N}+2\sum_{k=1}^N\frac{1}{k}$	(10)