あるアルゴリズムの時間計算量が $3n{\log }_{2}n+7{\log }_{2}n+4\sqrt{n}+10$ で表されるとき、これをオーダー記法で表したものはどれか。

解説

正解は「$O(n\log n)$」です。オーダー記法では、入力サイズ n を大きくしたときに最も速く増加する項だけを残し、係数や定数項は無視します。各項の増え方は $\log n<\sqrt{n}<n\log n$ の順に大きくなるので、支配的な項は $3n{\log }_{2}n$ で、係数3を除いて $O(n\log n)$ となります。対数の底の違いは定数倍の違いにすぎないため、底は省略します。「$O(\log n)$」は最も増加の遅い項だけを見た誤りです。「$O(\sqrt{n})$」は $\sqrt{n}$ の項を支配的な項と誤った場合です。「$O(n)$」は $n\log n$ の対数部分を無視した誤りで、$n\log n$ は n より速く増加します。