擬似コード「for i = 1 to n { for j = 1 to i { S } }」で、基本操作 S が実行される回数を表す式はどれか。

解説

正解は「$\frac{n(n+1)}{2}$」です。外側のループで i が1のとき内側は1回、i が2のとき2回、…、i が n のとき n 回実行されるので、合計は $1+2+\cdots +n=\frac{n(n+1)}{2}$ 回です。最高次の項は $\frac{n^2}{2}$ なので、時間計算量は $O(n^2)$ になります。「$n^2$」は、内側のループが毎回 n 回実行される場合の回数です。「$n$」は外側のループの回数だけを数えた誤りです。「$\frac{n(n-1)}{2}$」は、内側のループが j = 1 から i−1 までの場合、つまり各要素をそれより前の要素とだけ比べるような場合の回数です。