Last updated: Friday 5th September
2008, 7:46 PT by AHD

Machine-independent algorithm design
depends upon a hypothetical computer called the *Random Access Machine*
or RAM. Under this model of computation, we are confronted with a computer
where:

- Each "simple" operation (+, *, -,
=, if, call) takes exactly 1 time step.
- Loops and subroutines are
*not*considered simple operations. Instead, they are the composition of many single-step operations. It makes no sense for ``sort'' to be a single-step operation, since sorting 1,000,000 items will take much longer than sorting 10 items. The time it takes to run through a loop or execute a subprogram depends upon the number of loop iterations or the specific nature of the subprogram. - Each memory access takes exactly one time
step, and we have as much memory as we need. The RAM model takes no notice
of whether an item is in cache or on the disk, which simplifies the
analysis.

Under the RAM model, we measure
the run time of an algorithm by counting up the number of steps it takes on a
given problem instance. By assuming that our RAM executes a given number of
steps per second, the operation count converts easily to the actual run time.

The RAM is a simple model of how
computers perform. A common complaint is that it is too simple, that these
assumptions make the conclusions and analysis too coarse to believe in
practice. For example, multiplying two numbers takes more time than adding two
numbers on most processors, which violates the first assumption of the model.
Memory access times differ greatly depending on whether data sits in cache or
on the disk, thus violating the third assumption. Despite these complaints, the
RAM is an excellent model for understanding how an algorithm will perform on a
real computer. It strikes a fine balance by capturing the essential behavior of
computers while being simple to work with. We use the RAM model because it is
useful in practice.

Every model has a size range over
which it is useful. Take, for example, the model that the earth is flat.
You might argue that this is a bad model, since the earth is not flat. However,
when laying the foundation of a house, the flat earth model is sufficiently
accurate that it can be reliably used. Further, it is so much easier to
manipulate a flat-earth model that it is inconceivable that you would try to
think spherically when you don't have to.

The same situation is true with
the RAM model of computation. We make an abstraction that in general is very
useful. It is quite difficult to design an algorithm such that the RAM model
will give you substantially misleading results, by performing either much
better or much worse in practice than the model suggests. The robustness of the
RAM enables us to analyze algorithms in a machine-independent way.

Reference:
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK/NODE12.HTM