時間計算量が $O(n^2)$ のアルゴリズムで、入力サイズ n を2倍にすると、実行時間はおよそ何倍になるか。ここで、n は十分大きいものとする。

解説

正解は「約4倍」です。時間計算量が $O(n^2)$ のアルゴリズムでは、十分大きな n に対して実行時間がおよそ $n^2$ に比例します。入力サイズを2倍にすると $(2n{)}^2=4n^2$ となるので、実行時間は約4倍になります。全ての2要素の組を比較する処理や、単純なバブルソートがこれに当たります。「約2倍」は、実行時間が n に比例する $O(n)$ のアルゴリズムの場合です。「約8倍」は $(2n{)}^3=8n^3$ となる $O(n^3)$ のアルゴリズム、例えば素朴な行列積の場合です。「約16倍」は $O(n^4)$ の場合に当たります。オーダーが分かれば、入力サイズを変えたときの実行時間を見積もることができます。