Unit-Cost RAM, Word RAM and Bit Complexity as Three Different Machines

Every asymptotic statement carries a machine inside it, and the machine is usually left unstated. The same short expression can be O(1), O(n) or O(n²) depending on which operations the model charges for and what n counts. Sorting a list, adding two numbers and looking up a key in a hash table are each subject to this ambiguity, and the ambiguity decides whether an algorithm is considered competitive or hopeless.

One step per operation, operands unbounded

The simplest model gives a machine a fixed set of registers, unbounded memory addressed by integers, and a cost of one for every arithmetic operation, comparison, memory access and branch, regardless of the size of the operands. Under unit cost, adding two numbers is O(1), comparing two integers is O(1), and indexing an array is O(1). Almost every introductory analysis is a unit-cost analysis, and for good reason: it makes the operation count equal to the shape of the loop and produces bounds that are usually right up to a constant factor.

The model breaks when operands grow with the input. Adding two n-bit integers is one “operation” under unit cost, but on a physical machine it takes Θ(n/w) word operations for word size w. An algorithm performing Θ(n) such additions is linear in the unit-cost model and quadratic in bit operations. The gap is not a constant factor; it grows with the input.

Trial division is the standard casualty. Testing a number N for primality by dividing by every integer up to √N takes O(√N) unit-cost divisions, which is O(2^{n/2}) in the input length n = ⌈log₂ N⌉. The same algorithm is polynomial in one parameterisation and exponential in the other, and the exponential one is the honest description, because an input of n bits cannot be stored in less than n bits and no loop can outrun the storage that holds it.

Words as the unit

The word RAM model occupies the middle position. Registers and memory cells hold w bits, with w fixed by the setting, conventionally w = Θ(log n) for input size n, so that a single word can hold an index into the input. Arithmetic on words costs one, memory access costs one, and everything is measured in words. Because the word size scales with the input, the model avoids the pathology of an unbounded register while keeping a unit cost for operations that fit inside a word.

The choice w = Θ(log n) is principled rather than arbitrary. On a machine with n words of memory, an address needs ⌈log₂ n⌉ bits, and any machine that addresses its own memory must have registers at least that wide. A pointer-based structure on a 64-bit machine has w = 64, which corresponds to an input of up to 2^{64} words; for any input that fits in physical memory, w comfortably exceeds log n.

Operations that stay inside one word are the model’s strong suit: addition, comparison, bitwise operations, shifts by a constant. Operations that cross a word boundary, arithmetic on n-bit integers, comparisons of long strings, arbitrary-precision arithmetic, cost in proportion to the number of words touched. The bit model, sometimes called the log-cost or Turing machine model, drops the word structure entirely and charges per bit operation; it is the right model when the input is a number and its length is literally the bit count.

Three answers to one sorting problem

Sorting n integers that each fit in one word gives a clean demonstration of how much the model matters.

In the comparison model, the bound is Θ(n log n) comparisons by the decision-tree counting argument, and merge sort attains it. The model does not distinguish sorting 32-bit integers from sorting arbitrary-precision integers, because it does not let the algorithm look inside a key at all.

In the word RAM, radix sort with a radix of 2^r processes the keys in ⌈w/r⌉ passes of Θ(n + 2^r) work each, so a constant number of passes makes the whole sort Θ(n). Extracting a digit is a word operation and therefore free under the model. This does not contradict the comparison bound, because the comparison model forbids exactly the operation radix sort relies on.

In the bit model the input occupies n·w bits, so merely reading it costs Θ(nw) bit operations, and radix sort attains Θ(nw) up to a constant factor for a suitable digit size. The three answers are Θ(n log n), Θ(n) and Θ(nw).

Model	Charged unit	Sorting	Where it is the natural fit
Comparison model	one comparison of two keys	Θ(n log n)	algorithms defined by comparisons
Word RAM, w = Θ(log n)	word operation	Θ(n) for bounded keys	data structures
Bit model	bit operation	Θ(nw)	number theory, cryptography

None of the three is wrong. The question is what the analysis is meant to explain: a loop, a data structure, or a cryptographic primitive.

Multiplication, where the model is the result

Integer multiplication shows the consequences most sharply. Schoolbook multiplication of two n-bit integers takes Θ(n²) bit operations. Karatsuba’s method splits each operand into halves and performs three half-size multiplications instead of four, giving Θ(n^{log₂ 3}) ≈ Θ(n^{1.585}) by the recursion-tree argument. Fürer’s algorithm and its successors use fast Fourier transforms to reach n log n · 2^{O(log* n)}, a bound better than any fixed power of n but whose constants become relevant only at operand sizes far beyond ordinary library use.

Under unit cost, all of these collapse to “multiplication is O(1)”, which is the sentence an introductory course uses when comparing two sorting algorithms. Both statements are correct; they are about different machines. Confusion arises when a bit-complexity result is quoted as though it applied to unit-cost analysis. An algorithm with a better bit-complexity exponent can lose at every size a program will use, because it hides large constants and a complicated structure.

Hash functions split the same way. Under a word RAM with unit-cost multiplication, a multiplicative hash costs O(1). Under the bit model, multiplying two w-bit words is Θ(w²) by the schoolbook algorithm the hardware multiplier implements, or Θ(w^{1.585}) by Karatsuba. For w = 64 the difference is invisible, because the hardware executes a 64-bit multiply in a fixed number of cycles. The model boundary sits exactly where the hardware stops being able to do the operation in constant time, which is why the unit-cost model is defensible for word-sized operations and indefensible for arbitrary-precision ones.

# Same algorithm, three models: repeated addition to multiply.
def mul_by_adding(a, b):
    total = 0
    for _ in range(b):
        total += a          # unit cost: O(b) steps
    return total

# b fits in a word, so b <= 2**64. In the bit model the input length is
# len(a)+len(b) bits, and the loop runs 2**len(b) times: exponential.
print(mul_by_adding(3, 5))

The loop is linear in the value of b and exponential in its bit length, and the two descriptions are the same fact seen from two parameterisations. Stating the bound as O(b) is not false; it is incomplete, because it does not say that b is being measured as a magnitude rather than as a length.

The memory hierarchy the models all ignore

All three models charge a uniform cost for memory access, and all three are wrong in the same direction. A cache miss costs on the order of hundreds of cycles on current hardware while an L1 hit costs a handful, and the ratio has widened with every processor generation. The external-memory model, with its two levels and its block-size parameter B, and the cache-oblivious model, which has no explicit B and instead demands optimality for every B, exist to make this cost visible.

A matrix scan is the clearest case. Iterating a two-dimensional array in row order touches consecutive addresses; iterating in column order touches addresses n elements apart, which for a few thousand columns is far outside any cache line. Both loops perform the same number of additions, so all three models above assign them identical costs. In practice the column-major loop reads a fresh cache line for nearly every element, multiplying memory traffic by the ratio of cache-line size to element size, by a factor of 16 for 64-byte lines holding 4-byte elements. Blocking the computation into tiles whose working set fits in cache restores locality, and the arithmetic count does not change at all, which is the point: the improvement lives entirely in the hierarchy the standard models omit.

Stating the model with the bound

The model is part of the claim, and naming it takes a clause. For structures keyed on machine integers, the word RAM with w = Θ(log n) is conventional and makes hash tables and balanced trees comparable on equal terms. For algorithms whose input is a number and whose arithmetic exceeds a word, the bit model is the honest one, with input size measured in bits. For analyses about the shape of a loop and nothing else, unit-cost RAM is adequate, with the caveat that any operation whose cost grows with the input must be charged explicitly rather than waved through.

Two habits follow. First, state the input size in bits or in words, and name which operations are atomic. Second, when two published bounds for the same problem disagree, ask whether they answer the same question about the same machine, and then whether the difference matters at the sizes involved. Amortized bounds are subject to the same choice: a sequence can be measured in operations or in bit operations, and the amortized claim changes when the unit does. A bound that survives the change of model is a stronger result than one that holds in a single parameterisation, and the effort of saying which is which is small compared with the effort of discovering later that two numbers were never comparable.