##  [Random-Access Machine](/random-access-machine-0) 

 Definition

An abstract sequential machine model for algorithm analysis that represents a processor operating on an unbounded array of memory cells, each accessible in unit time by address, and a standard set of primitive operations; used to study time and space complexity under the assumption of unit-cost arithmetic and constant-time memory access.

 

 

 

 

 

 





## Principle

Principle

Treat algorithmic steps as operations on a central processor with constant-time indexed memory access and a fixed instruction set, isolating algorithmic cost from physical memory-layout concerns.

 

 

 

 

 





## Demonstration

Demonstration

Analyze an integer-sorting algorithm by counting the number of primitive operations (comparisons, assignments, memory loads/stores) executed on a RAM with direct addressing; express running time as a function of input size assuming each memory access costs one time unit.

 

 

 

 

## Misapplication

Misapplication

Assuming unit-time access for arbitrarily large integers stored in single cells without accounting for their bit-length, or applying RAM cost directly to models with hierarchical caches and nonuniform access latencies.

 

 

 

 

 





## Consequence

Consequence

Provides a simple, analytically tractable model that yields machine-independent asymptotic time and space bounds for sequential algorithms, facilitating comparisons between algorithms.

 

 

 

 

## Reversal

Reversal

A model that treats memory as strictly sequential-access (e.g., a Turing tape) where accessing the i-th cell may require time proportional to i, reversing the random-access assumption.

 

 

 

 

 





## Boundary

Boundary

Does not model parallel or distributed computation, cache hierarchies, or low-level hardware effects; conventions vary about whether arithmetic on unbounded integers is unit-cost; excludes stochastic or quantum resources.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Competes with the Turing machine model (fine-grained head movements and tape) and word-RAM variations (bounded word size), where notions of cost and memory unit differ.

 

 

 

 

 





## Synthesis

Synthesis

A simplifying sequential computation model that assumes constant-time indexed memory and primitive operations to focus algorithmic cost while abstracting away hardware details, suitable for asymptotic analysis when unit-cost assumptions are acceptable.