入力サイズ n が十分大きいとき、計算量を増加の小さい順に正しく並べたものはどれか。

解説

正解は「$O(n\log n)<O(n^2)<O(2^n)<O(n!)$」です。$n^2=n\times n$ で、$\log n$ は n よりはるかに小さいので、$n\log n$ の方が小さくなります。多項式の $n^2$ は指数関数 $2^n$ より遅く増加します。さらに $n!$ は、n が4以上で $2^n$ を上回り、その後も差が開き続けます。例えば n=10 のとき $2^{10}=1024$ に対し、10! は 3628800 です。「$O(n^2)<O(n\log n)<\cdots$」は最初の2つが逆です。「$O(n\log n)<O(n^2)<O(n!)<O(2^n)$」は最後の2つが逆です。「$O(n\log n)<O(2^n)<O(n^2)<O(n!)$」は多項式と指数関数の関係が逆です。