最悪時間計算量・空間計算量

アルゴリズム $A$ と入力 $x$ に対し、$A$ が $x$ 上で停止するまでに実行する基本演算の回数を $t_A(x)$、書き込みまたは読み出しを行った記憶セルの総数を $s_A(x)$ と書く。入力 $x$ のサイズ $|x|$ を、$x$ を表現するのに要する語数と定める。このとき

をそれぞれ $A$ の最悪時間計算量、最悪空間計算量と呼ぶ。