4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (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.) $\endgroup$ – greybeard Mar 30 '17 at 16:36
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Pratik Deoghare Mar 30 '17 at 16:37
5
$\begingroup$

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.

Another reason that we want machine words to be able to hold indices (even if we somehow modify the indexing operation to handle an index spread across several machine words) is that we want a loop of the form

for i from 1 to n:
     if i equals j then do something that takes O(1) time

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.