Model of Computation for Algorithm Analysis

Our analysis will be as independent as possible of the variations in machine, operating system, compiler, or programming language. We will call this mathematical model of computation, a random access machine or RAM.

  • A RAM is an idealized machine with an infinitely large random-access memory.
  • Instructions are executed one-by-one (there is no parallelism).
  • Each instruction involves performing some basic operation on two values in the machines memory.
  • We assume that each basic operation takes the same constant time to execute.

Disadvantages of this model

It does not model some elements

  • Efficiency due to locality of reference
  • Parallelism