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.
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$– greybeardAug 15, 2021 at 5:26
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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).
answered Aug 16, 2021 at 2:36
-
$\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$– aluAug 29, 2021 at 12:50
$\begingroup$
$\endgroup$
3
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$.
-
$\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