Space and time complexy of operations on 32-bit array vs. binary array

Question

Assume an array a of length $n$. I am wondering how to characterize the difference between time- and space complexity of 32-bit arrays of length $n$ and bit-arrays of length $n$.

Normally, you'd just state the array uses $O(n)$ space and algorithms run in $O(n)$, $O(n^2)$ and so on. But isn't there some difference between the two arrays?

I have read something about the word-size but I can't figure out how this fits into the picture..

PS. In an actual implementation (e.g Python). There is no difference between the space used by:

a1 = [1, 402, 303]
a2 = [1,0,1]

Right?

Answer 1

If you ignore the word size then both arrays use $\Theta(n)$ space. Remember that $32n = \Theta(n)$.

If your word has a (non-constant) length of $w$ bits and all the integers in a1 fit in a constant number of words (with no additional assumptions on their values), then a1 still uses $\Theta(n)$ words, while you can represent a2 using $\Theta(\lceil \frac{n}{w} \rceil)$ words (by packing groups of $w$ bits of a2 into a single word).

A common choice of $w$ in the word-RAM model is $w=\Theta(\log n)$.

In your Python example there is no difference between a1 and a2 since both lists are storing integers (using a fixed number of bytes that depends on the implementation and architecture, and assuming that the stored integers fit within the maximum integer representable using these bytes. Handling arbitrary precision integers is another story). However there might be ad-hoc types specifically designed to handle indexed collection of bits (e.g., bitsets).

Also, the language/implementation might optimize the array representation when it knows that it will store bits. This is the case, for example, of std::vector<bool> in C++, which can possibly reduce the space usage by some constant factor by packing bits into integers (as described above). For a fixed words size (e.g., 32 or 64 bits), this does not change the asymptotic space complexity.