比較モデル

キーの集合 $U$ に全順序 $\le$ が与えられているとします。アルゴリズムがキーについて行える操作が「2 つのキー $k, l$ を比べて $k < l$, $k = l$, $k > l$ のいずれであるかを知る」ことだけであるとき、そのアルゴリズムは比較モデルで動くといいます。キーの値を使った算術（下位ビットを取り出す、$(k - a)/(b - a)$ を計算する、など）は比較モデルでは禁止されます。

これに対し、キーをビット列とみなして算術や添字計算に使ってよい土俵を、ここではアドレス計算モデル（語 RAM モデル）と呼びます。整数の加減乗除・剰余・ビット演算と、配列の添字アクセスが 1 単位時間でできるものとします。これは 一様コスト RAM モデル（定義 2.1）［計算量と O 記法］ と同じ約束です。