Space complexity of function

Question

I'm new to working out space complexity and am stuck working out the following function

const isUnique = string => {
  if (string.length > 128) {
    return false
  }

  let seen = new Set()

  for (let i = 0; i < string.length; i++) {
    if (seen.has(string[i])) {
      return false
    }
    seen.add(string[i])
  }

  return true
}

Would it be O(n) as the set will grow in proportion to the size of the string? Or O(1) as it is a singe set no matter how large it gets and would never exceed 128 in length.

Thanks in advance for any help

Answer 1

Yes, it's constant because there's a maximum size that the set might have, regardless how large your input gets.

In fact, it would even still be constant if the string.length <= 128 restriction wasn't there, as long as the function expects a string and not an array of arbitrary items, as a string is characterised by being comprised of UTF-16 characters of which there is only a limited number - the set can never grow beyond the size of the alphabet, regardless how long the input is.