時間計算量が $O(2^n)$ のアルゴリズムを、1秒間に $10^9$ 回の基本操作を実行できるコンピュータで、n=50 の入力に対して実行する。基本操作の回数を $2^n$ 回とし、$2^{10}$ を $10^3$ とみなして近似したとき、実行時間はおよそどれくらいか。

解説

正解は「約12日」です。$2^{10}$ を $10^3$ とみなすと、$2^{50}=(2^{10}{)}^5$ は約 $10^{15}$ 回の操作になります。1秒に $10^9$ 回実行できるので、$10^{15}÷10^9=10^6$ 秒かかります。1日は86400秒なので、$10^6÷86400\fallingdotseq 11.6$ 日、つまり約12日です。「約17分」は $10^3$ 秒に相当し、n=40 の場合の値です。「約1秒」は n=30 の場合で、操作回数が約 $10^9$ 回のときです。「約32年」は $10^9$ 秒に相当し、n=60 の場合です。n が10増えるごとに実行時間が約1000倍になる点が、指数時間アルゴリズムの特徴です。