This part of the code is taken from the book "Breakdown of the book on coding."
public static boolean isUniqueChars2(String str) {
boolean[] char_set = new boolean[256];
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (char_set[val]) return false;
char_set[val] = true;
}
return true;
}
And the author mentions that
The time complexity is O (n), where n is the length of the string, and the spatial complexity is O (n).
I understand that the complexity of time is O (n), but I don't understand how the complexity of O (n) space can be
My thinking: char_set will remain an array of size 256, no matter what the size of the input (str). Even if the length of str is 100,000, char_set is still an array of 256 elements. Therefore, I thought that since the memory requirements for this function do not change with the input size and remain constant 256, the spatial complexity is constant, i.e. O (1).
Can someone explain if I am wrong (and why?)
.