Register model of computation

Question

It consists of one read only input memory and write only output medium. The computation proper takes place in a working memory of limited size. When stating that a problem can be solved with a certain number of bits, what we mean is that the working memory consists of that many bits. The input and working memories are divided into words of $w$ bits for a fixed parameter $w$. Random access to to input and working memory is provided. In the context of $n$ words, assume as is common , that $w = \theta(\log{n})$.

Question : What it means "In the context of $n$ words, assume as is common , that $w = \theta(\log{n})$. "

Link : " Space-efficient Basic Graph Algorithms Link"

Answer 1

The word RAM is a model of computation in which basic operations operate on words. For example, adding two words costs $O(1)$ in this model. In algorithms class, it is often tacitly assumed that basic operations on indices and on data cost $O(1)$. For example, consider the following program for computing the maximum of an array:

calculate-max(A, n):
max = A[1]
i = 2
while i <= n:
  if A[i] > max:
    max = A[i]
  i = i + 1

This program is usually assumed to run in $O(n)$. This means that the following operations should all cost $O(1)$:

• Assignment of data points (max = A[1], max = A[i])
• Assignment of indices (i = 2, i = i + 1)
• Comparison of indices (i <= n)
• Comparison of data points (A[i] > max)
• Arithmetic on indices (i + 1)

In order to accommodate this in the word RAM model, we need to assume that words have length at least $\Omega(\log n)$, since this is the length of indices such as i above. Usually words of length $\Theta(\log n)$ are enough for performance of an algorithm in the word RAM to match its performance as perceived by the algorithm designer. Therefore the most common word RAM model is the logarithmic cost word RAM, in which words have length $\Theta(\log n)$ (the constant doesn't matter since it only affects the running time by a constant factor).

The only remaining question is – what is $n$? It is usually assumed that $n$ is such that the input is $n$ words long. This definition is a bit circular (since the length of a word depends on $n$), but usually works out nevertheless.