配列の基本操作の計算量

長さ $n$ の配列 $A$ について、ワード RAM モデルの下で次が成り立つ。

1. 添字 $i$（$0 \le i \le n-1$）を指定した要素の読み出しと書き込みは $\Theta(1)$ 時間で行える。
2. 与えられた値 $x$ が $A$ に現れるかどうかを判定する探索は、要素の並びに順序の仮定がない場合、最悪 $\Theta(n)$ 時間を要する。先頭から順に比較する線形探索がこの計算量を達成する。
3. 位置 $i$（$0 \le i \le n$）への挿入は既存要素の移動をちょうど $n - i$ 回、位置 $i$（$0 \le i \le n-1$）の要素の削除は $n - 1 - i$ 回必要とし、いずれも $\Theta(n-i)$ 時間で行える。とくに最悪（$i = 0$）は $\Theta(n)$ であり、挿入位置 $i$ が $0, 1, \ldots, n$ 上一様分布に従うときの平均移動回数は $n/2$ である。