What is the space complexity of this string manipulation code?

Question

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.

I think you are right, but that the autor said that the original str self ocupy O(n) (or you are getting a copy by value?). — qPCR4vir
hmmm...thats interesting. I thought when deriving Asymptotic complexities we generally ignore how/where/when the input is read? And just concentrate on what's happening inside the method (taking into account the size of input, which is n) — anakkala
I'd like to see the author's reasoning. The space used by the algorithm itself is constant. You are right in that when we analyze space complexity, we're talking about the amount of extra space required by the processing, ignoring the input to the algorithm. — Jim Mischel
My copy (5th ed) of this book says O(1) space. I don't see it listed in the errata though. — brooksbp
I second @brooksbp comment. I have the 5th edition and it says O(1). I think it was revised in the later versions. — Rafay

Yamil Marques de Mello Yamil Marques de Mello · Accepted Answer · 2018-04-08T23:11:53

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.

What is the space complexity of this string manipulation code?

2 Answers