2
$\begingroup$

I don't know where else to ask this. And I don't know when or if I'll get reply at all if I comment on that answer. I was reading this answer on a text of CLRS and in the last line got confused. I understand with $c \lg n$ we can represent decimal numbers up to $n^c$. Does "index up to $n^c$" mean being able to store or represent up to $n^c$? Thanks in advance.

$\endgroup$
1
  • $\begingroup$ (with $c\lg n$ we can represent decimal numbers up to $n^c$ is taking $\lg$ excruciatingly literally.) In the first sentence of the hyperlinked contents (consider quoting the essential part), some T. Cormen uses index into arrays of size $n$ as an example. $\endgroup$
    – greybeard
    Aug 15, 2021 at 5:26

2 Answers 2

0
$\begingroup$

RAM machines typically allow access to an array using an index, which in many programming languages is done using the syntax A[i], where A is the array and i is the index. If your word size is $w$, then you can directly index this way $2^w$ words of memory (in the RAM machine, memory consists of machine words, whose size depends on the model; usually $O(\log n)$, where $n$ is the input size).

$\endgroup$
1
  • $\begingroup$ Thank you for this nice answer. I still need to think about it a little bit more to understand, then I'll accept it. $\endgroup$
    – alu
    Aug 29, 2021 at 12:50
0
$\begingroup$

If $b$ bits of storage are allocated to an integer variable $i$ that represents an index variable in your program, then the number of different values that $i$ can take is $2^b$. For example, if $8$ bits of storage space are allocated to a variable, then the variable can take values $0,1,2,\ldots,255$. Note that $\lfloor \log 255 \rfloor + 1 = 8$, where log’s are to base $2$. In general, representing the index $n$ will take $\lfloor \log n \rfloor + 1$ bits of storage space.

Thus, if the range of indices goes from $1$ to $n^c$, then roughly $\log n^c = c \log n$ bits of storage space are needed, and conversely, if $c \log n$ bits of storage space are allocated to an index variable then the index variable can take values up to $n^c$.

$\endgroup$
3
  • $\begingroup$ Representing $n>0$ values requires $\lceil \log_2 n \rceil$ bits. $\endgroup$ May 14 at 7:03
  • $\begingroup$ @YuvalFilmus Sure. That doesn’t seem to contradict what I wrote. Representing the index $n$ in $0$-based indexing means representing $n+1$ different values. $\endgroup$ May 14 at 7:17
  • $\begingroup$ In order to calculate the number of bits needed to store the values $0,\ldots,255$, we compute $\lceil \log_2 (255+1) \rceil$. $\endgroup$ May 14 at 10:19

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.