0
$\begingroup$

I am watching MIT's Introduction to Data Structure and there is something I'm not understanding at the 14:48 mark

Why does the machine word size, w have to be >= lg(n) where n is the length of a static array?

As I understand a static array, [1,2,3] is stored consecutively in the RAM like:

$$|*|*|1|2|3|*|*|*|$$

If each element in the array is stored in a word size w then wouldn't w have to be larger than lg(i)?

If I am storing a number equal to or smaller than 31, then the word size required is

$$w=ln(31)=5 ~bits$$

So as long as my array doesn't include an element >31 then wouldn't my word size be fine at 5 bits?

$\endgroup$

4 Answers 4

1
$\begingroup$

Maybe the lecture is assuming the Transdichotomous RAM Model. Under this assumption and with respect to algorithms involving arrays, you can access elements in $O(1)$, since this allows storing of indices in a single machine word. Because there are $n$ possible elements, at least $O(\log n)$ bits are needed to store an index $0 \le i \le n-1$. Note that this size is a lower-bound on the word size and $w$ can be bigger than $\log n$, to allow storage of values that are reasonably larger than $n$.

This $O(1)$ access time is quite reasonable in most cases and simplifies analysis of array operations since the running-time would just be counting the number of access.

$\endgroup$
5
  • $\begingroup$ Thanks for the answer. I still don't understand why the length of the array dictates the word size and not the array indices since each word contains one index. $\endgroup$
    – Nader
    Apr 2, 2023 at 23:26
  • $\begingroup$ @Nader hopefully the edit I made makes things clearer $\endgroup$
    – Russel
    Apr 2, 2023 at 23:41
  • $\begingroup$ So an array with ten 1 bit elements will have a lower bound of lg(10)? Even though each element is stored in a word $\endgroup$
    – Nader
    Apr 3, 2023 at 0:28
  • $\begingroup$ I do not understand your question. If you have 10 elements in your array then the word size must be at least $\lceil\log_2 10\rceil$ or 4 bits so you can store indices $0...9$ $\endgroup$
    – Russel
    Apr 3, 2023 at 2:19
  • $\begingroup$ The word size dictates the size of the largest possible array. $\endgroup$
    – gnasher729
    Apr 3, 2023 at 7:10
1
$\begingroup$

It’s the other way round: it’s not the array size determining the word size. It’s the word size determining the maximum possible array index and therefore the maximum array size.

Take for example a word size of 32 bits. A word can hold values from 0 to $2^{32}-1$.

Now you want an array with $2^{32}+1$ elements. According to the formula, the word size is too small or the array size is too large.

And you can see that you need an index of $2^{32}$ to access the last array element, which does not fit into a word. That’s the reason why the size of the largest array is limited.

You just confused yourself by looking at tiny arrays. This is about big arrays. A 16 bit processor cannot have arrays with more than 65,536 elements. A 32 bit processor cannot have arrays with more than about 4 billion elements and so on.

$\endgroup$
3
  • $\begingroup$ If the array element is what is being stored in the word then why does the number of elements matter. Each element in the array needs to be smaller than the word size, right? So you can't have a 5 bit element in a 4 bit word size $\endgroup$
    – Nader
    Apr 3, 2023 at 20:17
  • $\begingroup$ You got yourself confused from the very start. What is stored in array elements is totally, absolutely, one hundred percent irrelevant. I have had arrays with two elements of a megabyte each. It's ARRAY INDICES that are relevant here. $\endgroup$
    – gnasher729
    Apr 4, 2023 at 14:57
  • $\begingroup$ Isn't it always possible to increase the size of the array any given processor can handle, using bank switching? Unless, you define an array in the first place as meaning something directly and contiguously addressable with a single word (which necessarily means there can only be so many array cells as different values a word can hold)? $\endgroup$
    – Steve
    Aug 21, 2023 at 22:18
0
$\begingroup$

Word size determines the amount of memory that can be addressed. For example, if we have 4GB of RAM, then the word size should be 32 bits

 log2(4GB) = 31.89 bits, or 32 bits approximately
 word size to address 4GB should be >= 32 bits

So, it means in

$\endgroup$
1
  • $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Aug 31, 2023 at 22:48
0
$\begingroup$

You understand that $n=2^b$ numbers are stored at addresses $0$ to $n-1=2^b$.

What matters in this discussion is that the word size is a $\Theta(\log(n))$ function.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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