Word RAM

The word RAM model is an abstract machine similar to a random access machine, but with additional capabilities. It works with words of size up to w bits, meaning it can store integers up to size ${\displaystyle 2^{w}}$. Because the model assumes that the word size matches the problem size, that is, for a problem of size n, ${\displaystyle w\geq \log n}$, the word RAM model is a transdichotomous model. The model allows bitwise operations such as arithmetic and logical shifts to be done in constant time.[2] The number of possible values is U, where ${\displaystyle U\leq 2^{w}}$.

In the word RAM model, integer sorting can be done fairly efficiently. Yijie Han and Mikkel Thorup created a randomized algorithm to sort integers in expected time of (in Big O notation) ${\displaystyle O(n{\sqrt {\log \log n}})}$,[3] while Han also created a deterministic variant with running time ${\displaystyle O(n\log \log n)}$.[4]

The dynamic predecessor problem is also commonly analyzed in the word RAM model, and was the original motivation for the model. Dan Willard used y-fast tries to solve this in ${\displaystyle O(\log \log U)}$ time.[2] Michael Fredman and Willard also solved the problem using fusion trees in ${\displaystyle O(\log _{w}n)}$ time.[1]

• Transdichotomous model