1
$\begingroup$

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"

$\endgroup$
  • 1
    $\begingroup$ Where is the quote from? $\endgroup$ – Ariel Nov 17 '17 at 18:33
  • $\begingroup$ Please make sure to provide proper credit for your sources: see cs.stackexchange.com/help/referencing for how to reference your sources. $\endgroup$ – D.W. Nov 17 '17 at 20:04
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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