The word RAM is a model of computation in which basic operations operate on words. For example, adding two words costs $O(1)$ in this model. In algorithms class, it is often tacitly assumed that basic operations on indices and on data cost $O(1)$. For example, consider the following program for computing the maximum of an array:
calculate-max(A, n):
max = A[1]
i = 2
while i <= n:
if A[i] > max:
max = A[i]
i = i + 1
This program is usually assumed to run in $O(n)$. This means that the following operations should all cost $O(1)$:
- Assignment of data points (
max = A[1]
, max = A[i]
)
- Assignment of indices (
i = 2
, i = i + 1
)
- Comparison of indices (
i <= n
)
- Comparison of data points (
A[i] > max
)
- Arithmetic on indices (
i + 1
)
In order to accommodate this in the word RAM model, we need to assume that words have length at least $\Omega(\log n)$, since this is the length of indices such as i
above. Usually words of length $\Theta(\log n)$ are enough for performance of an algorithm in the word RAM to match its performance as perceived by the algorithm designer. Therefore the most common word RAM model is the logarithmic cost word RAM, in which words have length $\Theta(\log n)$ (the constant doesn't matter since it only affects the running time by a constant factor).
The only remaining question is – what is $n$? It is usually assumed that $n$ is such that the input is $n$ words long. This definition is a bit circular (since the length of a word depends on $n$), but usually works out nevertheless.