アルゴリズム解析
大まかに言えば、あるアルゴリズムの入力サイズ n がある特定の値を超えたとき、その成長率がある数学関数のオーダーであるとは、その関数 f(n) に正の定数をかけた値がそのアルゴリズムの実行時間の上限(英語版)を与えることを意味する。言い換えれば、入力サイズ n が n0 より大きいとき、そのアルゴリズムの実行時間は c × f(n) を越えない(cは定数)。この概念はO記法で表現されることが多い。例えば、挿入ソートの実行時間は二次関数的に成長(英語版)するので、挿入ソートのオーダーは O(n) と言える。
O記法はアルゴリズムの最悪の場合を表現するのによく使われるが、平均的なケースを表すのに使われることもある。例えばクイックソートの場合、最悪では O(n) だが、平均では O(n log n) となる。
非効率なアルゴリズムを使用したためにシステム性能に重大な影響を与えることがあるため、アルゴリズム解析は実用的な意味でも重要である。
(その時点での計算機のスペックとの相対として)膨大なデータを扱う場合、そのオーダーによっては、非効率なアルゴリズムは役に立たない。非効率なアルゴリズムは、たとえば時間や記憶領域を無駄に浪費する。
一方で、ただ単に「実行時間が重要な用途だから」というだけでアルゴリズムに凝るのは、大抵は単なる無駄である。例えば探索について、配列に全て放り込んで、端から探すだけという単純な実装が、データ数が少ない場合にはそれが最も実行時間が少ない、という場合も多い。実例としてはUnixのディレクトリエントリの扱いは古くはそのような実装であった。ボトルネックになる、あるいは膨大なデータになると、あらかじめ確実にわかっているのでなければ、改良する余裕のある、しかし単純な設計でまずは実装し、計測・測定の後に効率化にとりかからなければならない。