quickselectの平均計算量は本当にnなのか？

　そもそもpartitionを1回するだけで計算量はnかかるんじゃない？quickselectってほんとにそんなに計算量少ないの？疑問が湧いてきたので確かめてみる。
　配列サイズをnとして、partitionの計算量はn-1だ。では、partitionをかけるべき配列サイズはどのように小さくなっていくのだろうか？
　k回目のpartition対象となる配列サイズをn_kとすると、n_k+1 = (n_k - 1)/2となる。ここからn_kを求める解法は高校時代に習ったような気もするが、さすがに昔過ぎて、もう覚えてない。しかし、じっと式を睨んでいると、n_k = n / 2^k + Σ(1/2)^iと出た。（ただしΣはi=1からk）
　Σの部分は等比数列の和の公式…とかは覚えてないけど、解き方は覚えているので適当に計算すると1 - (1/2)^kと出た。結局、n_k = (n+1)/ 2^k - 1という感じか。
　では、繰り返しの回数はどうなるのか？n_k>3の間はやらねばならない。というわけで、n_k>3を解くと、k < log(n+1)-2と出た。回数はlogで抑えられるらしい。なんとなくそれっぽい。
　で、i=0からkまでの総計算量を計算してみると、(n+1)(1-1/2^k) - 2kとなった。最もオーダーの大きな部分を取り出すとn。（繰り返しの回数はあんまり関係なかった…。）結局、quickselectの平均計算量は配列サイズに比例する、ということで良いらしい。なんか釈然としないけど。