What is the spatial complexity of this string manipulation code?

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?)

.

+5
1

, :

, - , - , .

, - O (1), , , O (n).

0

All Articles