中央値の中央値
この「良いピボット値」では、全ての要素を一定の割合でより大きい値と小さい値に分割することができ、つまり探索対象の要素数を一定の割合で減らすことができ、ゆえに要素数が指数関数的に減少して、全体的な計算時間は線形のままとなる。
中央値は、そのような「良いピボット値」であり、各段階で探索対象を半分ずつに減らすことができる。ゆえに、もし中央値を線形時間で計算できるなら、各段階では線形時間しか増えないので、全体の計算量は線形時間のままとなる。
中央値の中央値アルゴリズムでは、正確な中央値ではなく、代わりに、30から70パーセンタイルの間(第4十分位数の中間)点であることが保証されたおおよその中央値を使用する。そのため、探索対象の要素数は各段階で一定の割合(最小で30%)で減少する(つまり最大で70%が残る)。 一方、ピボット値計算の増加量は各段階では線形となる(元の探索対象の要素数の20%の要素に対する再帰と、線形時間の和)。よって、各段階で問題の要素数は元の要素数の90%(20%+70%)という一定の割合で削減されるので、全体としての計算量は、要素数 n {\displaystyle n} に対して線形 O ( n ) {\displaystyle \mathrm {O} (n)} である(線形性の厳密な証明は後述)。