CODEWITHSUNDEEP
javaalgorithmspace-complexity
antonro
antonro

Reputation: 469

Why is the space complexity for this algorithm to check if an array has all unique characters O(n)?

In the book "Cracking the Coding Interview", first exercise says "Implement an algorithm to determine if a string has all unique characters (not using additional data structures)". And the solution:

public static boolean isUniqueChars(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;
}

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

I don't see why space complexity is O(n). The array char_set has a constant length, independent on how long the given str is. To me, space complexity is O(1).

Upvotes: 1

Views: 281

Answers (1)

OmG
OmG

Reputation: 18838

Its space complexity is O(1) (\Theta(1)) as it keeps 256 (constant) bits more than the size of the input array. Also, the time complexity is O(1) as there are 256 chars to be checked in the input string and the duplicate will be detected at most at 256th character of the string.

Upvotes: 2

Related Questions