# What does "index up to $n^c$" mean in this question about CLRS "word size $c \lg n$"?

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.

• (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. Aug 15, 2021 at 5:26

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).

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

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$$.

• Representing $n>0$ values requires $\lceil \log_2 n \rceil$ bits. May 14 at 7:03
• @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. May 14 at 7:17
• In order to calculate the number of bits needed to store the values $0,\ldots,255$, we compute $\lceil \log_2 (255+1) \rceil$. May 14 at 10:19