RAM Model

RAM stands for random access machine. This computational model is similar to that of a pointer model and can be considered to be a multiple register counter machine with indirect addressing. Addressing in this computational model relates to either gathering an address directly from an instruction in its finite state machine table, or deriving the address from the contents of the location which the instructions refer to.

Registers are locations with a unique address and content that is a natural number.

The variation of the RAM model used in this algorithm allows for the implementation of bitwise Boolean operators and utilizes Boolean AND,OR,XOR operators alongside the usual addition, subtraction, multiplication and comparison instructions.

In the article by Fredman and Willard (1993), they found that using fusion trees with such a computational model, they were able to construct a linear space O(NlogN/loglogN) worst case time-sorting algorithm and when including randomization and integer division, dynamic searching and sorting could be reduced to O((logN)^1/2) and O(N(logN)^1/2) respectively.