What is the space complexity of this string manipu

问题:

This piece of code is from Cracking the Coding interview book.

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,

Time complexity is O(n), where n is the length of the string, and space complexity is O(n).

I understand time complexity being O(n) but I don't understand how could space complexity be O(n)

My thinking: char_set will remain an array of size 256 no matter what the input (str) size is. Even if the length of "str" is 100,000, char_set is still a 256 element array. So I thought, since memory requirements for this function does not change with the size of the input and remain a constant 256, the space complexity is constant, i.e., O(1).

Can someone explain, if I am wrong (and, why?)

Thank you so much.

回答1:

it's a bit more complicated, i think:

the max number of iterations before some character will be encountered twice is the size of the alphabet the string is built over.

if this size is finite, time complexity is O(1), if it's not, the boolean array cannot be of finite size, thus, space complexity will be O(n).

回答2:

The space complexity in that example is O(N) because the string is received as parameter; we don't know exactly it's size, and taking into account that the space complexity advices about the memory consumption in time of the algorithm, it will vary depending on the size of "str". Because of that N should be used.

Exactly the same happens if I have for example:

public void someMethod(int a[], char s, int w){...}

It will be O(N) because of "a[]" (we don't know it's size).

On the other hand:

public void someMethod(char s, int a, int x){...}

It will be O(1) (constant). Due we already know the memory allocated for the necessary attributes.

Hope it helps.