アルゴリズム解析
アルゴリズム解析とは、アルゴリズムの実行に必要とされるリソース（時間や記憶領域）量を見積もることである。多くのアルゴリズムは任意長の入力を受け付けるよう設計されている。アルゴリズムの「効率」や「複雑さ」は一般に、入力長からそのアルゴリズムを実行するのに必要なステップ数（時間複雑性）や記憶領域サイズ（空間複雑性）への関数として表される。
アルゴリズム解析は計算複雑性理論の重要な一分野である。計算複雑性理論では、与えられた計算問題を解くアルゴリズムが必要とするリソースを理論的に見積もる。この見積もりにより効率的なアルゴリズムを設計する指針が得られることがある。
アルゴリズム解析ではふつう、漸近的（asymptotic）な意味で複雑性を見積もる。すなわち、ある程度大きな入力長の際の複雑性関数を見積もる。このためにO記法、Ω記法、Θ記法が用いられる。例えば、二分探索のステップ数は入力サイズの対数に比例し、これを O(log(n)) と表記したり、「対数時間」と称したりする。このような漸近的な見積もりを用いるのは、同じアルゴリズムでも実装の違いにより差が出るのを捨象するためである。異なる妥当な実装による効率の違いは定数倍に留まる。この定数を隠れた定数（hidden constant）と呼ぶ。
漸近的でない正確な効率がわかる場合もあるが、そのためには「計算モデル」と呼ばれるアルゴリズムの特定の実装を仮定する必要がある。計算モデルはチューリング機械のような抽象化された機械を使うか、個々の命令の実行時間が変化しないと仮定することが多い（例えば実際のコンピュータではキャッシュにヒットするかしないかでは大きく実行時間が異なるが、アルゴリズム解析では一般にそれを無視する）。例えば、二分探索で N 個のソートされた数から探索する場合、1回の参照を一定の単位時間でできるとした場合、回答を得るまでに最大で log₂ N+1 単位時間を要する。
実行時間解析
実行時間解析とは、アルゴリズムの入力サイズ（通常 n と記される）が増大したときの実行時間の増大を評価し推定することで、アルゴリズムを理論的に分類することである。実行時間効率は計算機科学の重要な関心事である。プログラムが完了するまでに数秒で済むのか、数時間かかるのか、1年以上かかるのかは、実装したアルゴリズムに依存する（アルゴリズムの実行時間を実測して解析するのは性能解析と呼ばれる）。
成長のオーダー
大まかに言えば、あるアルゴリズムの入力サイズ n がある特定の値を超えたとき、その成長率がある数学関数のオーダーであるとは、その関数 f(n) に正の定数をかけた値がそのアルゴリズムの実行時間の上限を与えることを意味する。言い換えれば、入力サイズ n が n₀ より大きいとき、そのアルゴリズムの実行時間は c × f(n) を越えない（cは定数）。この概念はO記法で表現されることが多い。例えば、挿入ソートの実行時間は二次関数的に成長するので、挿入ソートのオーダーは O(n²) と言える。
O記法はアルゴリズムの最悪の場合を表現するのによく使われるが、平均的なケースを表すのに使われることもある。例えばクイックソートの場合、最悪では O(n²) だが、平均では O(n log n) となる。
他のリソースの成長率解析
実行時間解析の方法論は記憶領域の使用量などの成長率の推定にも応用できる。例えば、あるファイルの大きさに基づいて使用するメモリの確保量を変更するプログラムの擬似コードは次のようになる。
while (ファイルはオープン中)
    let n = ファイルのサイズ
    for ファイルサイズが100,000キロバイト増加するごとに
        確保するメモリ量を倍にする
この場合、ファイルサイズ n が増大するとメモリ使用量は指数関数的成長を示し、そのオーダーは O(2ⁿ) となる。
意義
非効率なアルゴリズムを使用したためにシステム性能に重大な影響を与えることがあるため、アルゴリズム解析は実用的な意味でも重要である。実行時間が重要な用途では、時間のかかり過ぎるアルゴリズムは役に立たないことがある。非効率なアルゴリズムは時間や記憶領域を無駄に浪費することもある。