# CLRS RAM model Description

I'm seeking some clarification on a description of the RAM model in CLRS on page 23, section 2.2 (Analyzing Algorithms).

Firstly, it is mentioned that we assume integers are represented with $c\cdot\log_2 n$ bits for some constant $c\geq 1$. Now take the integer value $2$, would it not be the case that we would need more than $\log_2 2=1$ bit to represent the integer value $2$? Since we must express two as $(10)_2$? Perhaps the constant $c$ is supposed to account for this discrepancy.

Secondly I'm a bit confused by this statement: "We require $c \geq 1$ so that each word can hold the value of $n$, enabling us to index the individual elements...". I understand that if $c$ were $0$ or negative then that would not make any sense, however, are we also to assume then that $c$ must be an integer?

Any intuitive descriptions of these basic properties would be great or relevant examples someone can come up with.

• (The argument may get worse trying to represent integral numbers up to 1. Note that c is allowed to be larger than one, e.g., 3. With $\log _2 n$ not necessarily an integer, restricting c wouldn't help.) Commented Mar 30, 2017 at 16:36
• Its not about representing number 2. Its about labelling 2 things with unique labels of minimum length using only 2 (base) symbols. If you had two things you can label one with 0 and another with 1. So each thing will have label of length $1 = \log_2(2)$. Commented Mar 30, 2017 at 16:37

In the RAM model, variables hold a machine word, and operations on machine words take $O(1)$ time. The question is how big should a machine word be. In the variant of the RAM model used in CLRS, a machine word should be large enough so that a variable can count from 1 to $n$ (this is the meaning of the phrase "enabling us to index the individual elements"). To count from 1 to $n$ you need roughly $\log_2 n$ bits, or more accurately, $\log_2 n + O(1)$ bits. This is why we need $c \geq 1$; note that $c$ need not be an integer.
In the RAM model, indexing an array requires that the index is held in a single variable (or at least, this is one reasonable definition). This is why it is important that the machine word is large enough to index all arrays that could appear in an algorithm. If we only consider polynomial time algorithms, then all arrays have polynomial size, and so require indices of size $\Theta(\log n)$. This is the bare minimum needed to make the RAM model useful. It turns out that a larger machine word is not usually necessary, and so $\Theta(\log n)$ is a good choice.
for i from 1 to n:

to run in time $O(n)$. This implies that the operation of incrementing an index should be $O(1)$, and that the operation of comparing two indices should be $O(1)$. So we want our machine words to be large enough to contain an entire index.