Space complexity while using set instead of array-CodePudding

Let's suppose we have an ASCII-string (256 symbols) and we should determine whether all of the characters are unique. As a solution such pseudocode was suggested.

var array = Array(repeating: false, count: 256)
for chr in s {
    if array[chr.asciiValue] {
        return false
    }
    array[chr.asciiValue] = true
}
return true

It is said that array with 256 elements is O(1) space because it has fixed size. But what if I use set instead of array. Will it still be O(1) since maximum count of elements will be fixed (256) and it won't depend on the size of input string?

Thanks in advance!

CodePudding user response：

Your array looks like a dictionary data structure.

Perhaps set in your language is based on a dictionary too, and has the same space complexity O(1) (more exactly O(alphabet_size))

CodePudding user response：

Most people would agree that the space complexity is still O(1) when you use a set, because the number of elements is bounded.

This is a bit of a gray area, though.

Imagine that, instead of a string, you had a list of integers, which are 32-bit on your machine, and that the sizes of things are stored in integers of the same size.

Now lets consider your two choices again:

We certainly say that the set implementation is O(n), since each entry in the list may be different, and in that (worst) case, the set size will grow linearly with the list size.
Alternatively, we could use the array implementation. We'll allocate a bit for each integer, so the size of that array will be exactly 512MB. The space (and time!) complexity of this implementation is still O(1), even though it is worse that the set implementation for probably every list you'd see in practice.

When comparing these implementations, it would not be useful to state the complexity of the set implementation as O(n) and the array implementation as O(1)!

Thankfully, these problems don't really present in practice, because when we make such statements, our intent is to communicate useful information. We would take the alphabet size (say k) into account, and say that the set implementation has space complexity O(n), while the array implementation has space complexity O(k).