中央値の中央値
先述の通り、本項で説明した中央値の中央値アルゴリズムでは、配列全体を5要素ずつの小配列に分割した。5要素ずつに分割した理由については以下のように説明できる。
奇数個の要素から成る小配列に分割するのが高速かつ簡便なため。偶数個の要素から成る小配列に分割することもできるが、その場合、真ん中の要素は2つになってしまい、中央値はその平均をとらなければならないので、唯一の中央値を簡単に選択できる奇数個に比べて遅くなる。
中央値の中央値アルゴリズムが動くのは1つの小配列には5要素以上が必要なため。もし3要素ずつしかない場合、小配列の中央値を抽出した配列の要素数は 1 3 n {\displaystyle {\frac {1}{3}}n} 個になる。また、各小配列の中に存在するピボット値以下・以上の値はそれぞれ2つずつとなるので、次の探索対象の配列は要素数が最悪でも 1 3 n × 1 2 × 2 = 1 3 n {\displaystyle {\frac {1}{3}}n\times {\frac {1}{2}}\times 2={\frac {1}{3}}n} 個減少するので、残るのは ( 1 − 1 3 n ) = 2 3 n {\displaystyle \left(1-{\frac {1}{3}}n\right)={\frac {2}{3}}n} 個となる。ゆえに、結局、前者と後者を合わせて n {\displaystyle n} 個の要素に対して選択アルゴリズムを必要としてしまうので、要素数が全く減らないことになる。
C n {\displaystyle Cn} の項は、ピボット値を使って配列を2分割して次の探索対象の配列を作成するための処理時間(ピボット値と各小配列から中央値のみを抽出した配列の各要素との比較処理であり、比較処理は定数時間 O ( 1 ) {\displaystyle \mathrm {O} (1)} で計算可能であるので):計算手法で示したコード上では、初回の反復におけるPartitionの処理時間
T ( 7 10 n ) {\displaystyle T\left({\frac {7}{10}}n\right)} の項は、分割した後の次の探索対象の配列(要素数は最悪でも元の配列の要素数の7割)でk番目に大きい要素を計算する最大の処理時間(クイックセレクトを再帰的に適用することと等価なので):計算手法で示したコード上では、次の反復以降にかかる処理時間。
この式は簡単に解けて、最終的には以下のように線形時間 O ( n ) {\displaystyle \mathrm {O} (n)} であることを示すことができる。
T ( n ) ≤ 10 C n ∈ O ( n ) {\displaystyle T(n)\leq 10Cn\in \mathrm {O} (n)}