The Space Complexity of Sets

In discussing time or space complexity, we typically use the variable N to represent how many pieces of data we’re dealing with. In the context of sets, N would represent the number of elements our set contains.

A hash table set has a space complexity of O(N) since the hash table’s space is (constants aside) tailored to hold the set’s N elements in N cells.

However, with Boolean arrays and bit vectors, the number of values they represent corresponds not to the number of values in our set, but rather the range of possible set values. So, even if a set has five values, if those values fall in a range from 0 to 1000, our Boolean array has to hold 1,000 integers. To signify this, I’m going to use the variable R to represent the number of possible values in the range.

So, a Boolean array has a space complexity of O(R), as it holds up to R Boolean values of True or False.

A bit vector, on the other hand, can fit 32 values inside each of its integers on a 32-bit machine. Because this number can vary from machine to machine, we’ll use the variable B to signify the number of bits that each integer holds.

It turns out that a bit vector stores a total of R/B integers. For example, if the range is 256, and the number of bits in an integer is 32, a bit vector needs only to contain 8 integers. This is because 256 / 32 = 8.

Accordingly, we’d say that the space complexity of a bit vector is O(R/B). Some literature out there may use different variable names instead of R or B, but you get the idea.