>>14
厳密な証明じゃないけど、入力(ソートする配列)のサイズを n として、パーティションのステップで n 、結果としてサイズ n/2 の配列が2つできる。2つのサイズ n/2 の配列に対してそれぞれクイックソートするから、合わせると

T(n) = n + 2T(n/2)

= n + 2{ n/2 + 2T(n/4) } = 2n + 4T(n/4)
= 2n + 4{ n/4 + 2T(n/8) } = 3n + 8T(n/8)
...
// 繰り返すと以下のようなパターンが見えてくる
...
= kn + 2^k * T(n / (2^k)) --------- (*)

になる。
T(n/(2^k)) の n / (2^k) が 1 になるとき、n = 2^k <---> k = log n

k = log n を (*) の式に戻してやると

= kn + 2^k * T(n / (2^k))
= n log n + n * T(1)
= O (n log n)