中央値の中央値
クイックセレクトは分割統治法であり、計算の各段階で、残っている探索対象の要素が n {\displaystyle n} 個の場合に O ( n ) {\displaystyle \mathrm {O} (n)} の計算時間を必要とする。そのためクイックセレクト全体の計算量は、
もし探索対象の要素数を(一定の割合で)指数関数的に減少させられるなら、等比級数と1段の計算量( O ( n ) {\displaystyle \mathrm {O} (n)} )の積、つまり線形時間 O ( n ) {\displaystyle \mathrm {O} (n)} となる。
しかし、要素数の減少がとても遅い(例えば、減少する要素数が一定、最悪の場合1つずつしか減らないような線形減少の)場合、各段の計算量の線形和となり、2次時間 O ( n 2 ) {\displaystyle \mathrm {O} (n^{2})} となる(三角数は2次となる)。
最悪時間となる場合は、例えば、各段階でピボット値として最小値を選んでしまう時である。これは、既に降順に並べ替え済みの配列に対して、最初の要素をピボット値として選択してしまうと実際に起こりうる。
つまり、もし各段階で一貫して「良いピボット値」を選択し続けられるなら、このような最悪の場合を回避することができ、最悪の場合でも線形時間の性能となる。