アルゴリズム解析
外側のループの次の反復では、j は 1 から 2 まで変化する。内側のループは2回通るので、内側ループ本体(ステップ6)にかかる時間は 2T6、内側ループの条件(ステップ5)にかかる時間は 3T5 となる。
要するに、内側ループの本体にかかる時間は、次のような等差数列で表される。
T 6 + 2 T 6 + 3 T 6 + ⋯ + ( n − 1 ) T 6 + n T 6 {\displaystyle T_{6}+2T_{6}+3T_{6}+\cdots +(n-1)T_{6}+nT_{6}}
この式は次のように因数分解できる。
T 6 [ 1 + 2 + 3 + ⋯ + ( n − 1 ) + n ] = T 6 [ 1 2 ( n 2 + n ) ] {\displaystyle T_{6}\left[1+2+3+\cdots +(n-1)+n\right]=T_{6}\left[{\frac {1}{2}}(n^{2}+n)\right]}
内側のループの条件部にかかる時間の総計も同様に次のように得られる。
2 T 5 + 3 T 5 + 4 T 5 + ⋯ + ( n − 1 ) T 5 + n T 5 + ( n + 1 ) T 5 {\displaystyle 2T_{5}+3T_{5}+4T_{5}+\cdots +(n-1)T_{5}+nT_{5}+(n+1)T_{5}}
アルゴリズムはプラットフォームに依存しない(すなわち、アルゴリズムは任意のオペレーティングシステムが動作する任意のコンピュータ上で任意のプログラミング言語で実装できる)ので、複数のアルゴリズムの性能を比較するのに経験的技法(実測値)を用いるのはあまりにも問題が多い。
例として、大きさ n のソートされたリストから特定のエントリを検索するプログラムを考える。そして、最新型の高性能なコンピュータAでは線型探索アルゴリズムでプログラムを実装し、古い低性能なコンピュータBでは二分探索アルゴリズムでプログラムを実装したとする。それら2つのコンピュータでそれぞれのプログラムのベンチマークテストを実施し、次のような結果が得られたとする。
この測定結果を見ると、コンピュータAで実行したアルゴリズムの方がコンピュータBのそれよりも遥かに高速だと結論しそうになる。しかし、入力リストの大きさを十分大きくすると、その結論は全くの間違いだったことが判明する。
線型探索プログラムを実行したコンピュータAでの成長率(実行時間の増加率)は線型性を示す。すなわち、そのプログラムの実行時間は入力サイズに比例している。入力サイズが2倍になれば実行時間も2倍になり、入力サイズが4倍になれば実行時間も4倍になる、という具合である。一方コンピュータBでは二分探索プログラムを実行したので、成長率は対数的になる。入力サイズが2倍になったとき、実行時間の増加は一定である(この例では25,000ナノ秒)。表面上コンピュータAの方が高速でも、コンピュータBの方が成長率が低い(遅い)ので、入力サイズが大きくなれば必然的にコンピュータBの方が勝つことになる。