漸化式 $T(n)=2T(n/2)+cn$（c は正の定数、$T(1)=c$）で表される時間計算量のオーダーはどれか。

解説

正解は「$O(n\log n)$」です。この漸化式は、サイズ n の問題をサイズ n/2 の2つの部分問題に分けて解き、その結果を cn の手間で組み合わせることを表し、マージソートの計算量に当たります。展開すると、再帰の各レベルで手間の合計は常に cn で、問題のサイズが半分ずつになるためレベルの数は約 ${\log }_{2}n$ です。よって全体で $cn{\log }_{2}n$ となり、$O(n\log n)$ です。「$O(n)$」は1レベル分の手間しか数えていません。「$O(n^2)$」は、$T(n)=T(n-1)+cn$ のようにサイズが1ずつしか減らない場合の解です。「$O(\log n)$」は、$T(n)=T(n/2)+c$ となる2分探索の場合の解です。