Big O space complexity of this isAnagram method

Question

I'm currently debating with some friends what is the Big O space complexity of this isAnagram method:

public boolean isAnagram(String firstWord, String secondWord) {
    if(firstWord == null || secondWord == null || firstWord.length() != secondWord.length()) {
        return false;
    }

    Map<Character, Integer> charCounts = new HashMap<>();
    for(char c1 : firstWord.toCharArray()) {
        if(charCounts.containsKey(c1)) {
            int currentCount = charCounts.get(c1);
            charCounts.put(c1, currentCount + 1);
        } else {
            charCounts.put(c1, 1);
        }
    }

    for(char c2 : secondWord.toCharArray()) {
        if(charCounts.containsKey(c2)) {
            int currentCount = charCounts.get(c2);
            if(currentCount == 0) {
                return false; // not an anagram if it has more of one character than the first word
            }
            charCounts.put(c2, currentCount - 1);
        } else {
            return false; // not an anagram if it contains another character
        }
    }
    return true;
}

It's a point of contention because the space used by the method doesn't exactly depend on the input, but a characteristic of the input, namely the number of unique characters in the firstWord.

Let's say m is the length of the first word, and n is the length of the second word. Let's say that k is the number of unique characters in firstWord.

Some of us think that the space complexity is O(k), essentially the number of entries in the map. That is: k is the upper bound on the space used, because k will be the number of entries created in the map, one entry for each unique character.

Some think, it's basically just an O(1) space complexity, because even though the map is dynamically sized in reality, we could also think of it as O(1) and actually just pre-populate the map with counts of 0 for all possible alphabet. The argument against this is that you don't know "all possible alphabet" when latin alphabet is 26 characters, but ascii has 128, and unicode has > 137,000, and other character sets, who knows?

Others argue that we should take into account only m, the length of the first word. In some cases m < k, because it is shorter than k. In the worst case, m > k (because of duplicate characters) and, in very long strings, m will determine the choice of the type of the map's values. e.g. The code given uses "Integer" or 2^32 size counts, but you may need to go to 2^64 or even larger on very long strings. At any rate, this argument contends that m is a factor in how the algorithm scales and so it should be O(m).

A derivative of this last argument is that, on average, for any given character, there are m/k occurrences of that character in the string and the size of a value m/k in computer space is log(m/k), therefore a tighter Big O is O(k * log(m/k)).

Does anyone have any thoughts?

Answer 1

You probably expected the following answer.

Everyone of your friends is correct from her/his own perspective.

All you need to realize is that complexity analysis depends on lots of assumptions. In many cases, those assumptions have been defined beforehand or different assumptions will not not affect the end result of time-complexity analysis and space-complexity analysis. So people usually do not even mention those assumptions, especially in situations where the assumptions are stated or illustrated beforehand such as at the start of a chapter or a course. However, from time to time, situations arise where those assumptions are unclear, debatable, missing or even plainly invalid. Once you have made it clear what are the assumptions, including the model of computation used, there should be no real conflict.

Let us check each perspective raised in the question.

"The space complexity is $O(k)$", where "$k$ is the number of unique characters in firstWord". This observation points out the basic quantity in space usage.

"It's basically just an $O(1)$ space complexity", which make sense if we assume the input come from a vocabulary with a bounded number of characters. This is consistent with (almost?) all natural languages, whose number of characters are bounded while words or strings can be created as long and as many as we wanted, if only for the purpose of playing IsAnagram. Note this proposition can be seen as the previous proposition applied to refined but very common situations.

"It should be $O(m)$", where "$m$ is the length of the first word". There is hardly any argument against the correctness of this more relaxed bound, although it may seem not as tight as other bounds.

"On average, for any given character, there are $m/k$ occurrences of that character in the string and the size of a value $m/k$ in computer space is log(m/k) therefore, a tighter big $O$ is $O(k\log(m/k))$". This bound is based on the sharper observation that a number consists of many bits. Instead of counting the number of numbers used, it counts the number of bits used. (To prove that bound is correct, a dose of non-trivial math is needed.) The positional number system is about the optimal system to represent integers in term of space usage in this world, a fact that is reflected in the $\log$ factor. It can hardly considered anywhere near the physical truth without that factor. This line of reasoning is interesting as it indicates a more realistic model of computation than the more-commonly-used models of computations as implied in virtually every tutorial for elementary complexity analysis ([1], [2], [3]), where any integer is considered occupying a unit of space for the sake of simplicity and uniformity. Those common models include the family of register machines that includes counter machine and random-access machine. That is why we rarely see that $\log$ factor showing up in most complexity analysis. Unless required explicitly, we usually ignore that factor in space-complexity analysis and time-complexity analysis on our daily programming. On the other hand, that factor has to be taken into consideration, for example, in the bit by bit analysis of the Turing machines (Why do we reject Turing machines that use space less than the log of the length of the input?).

You might insist asking, which answer makes sense most? Well, even though I might have my personal preference, a single choice will appear opposite to the whole point of this answer. Each and every one of them is valid under their respective assumptions and useful in different situations. Of course, if you are in an exam, do remember the default assumptions in your course!

---

As you must have noticed, I have inserted time-complexity in this answer. That is because we could have similar contention over the time-complexity of many algorithms. The usual resolution will be the same: state the assumptions clearly and we can happily accept each other's view, even though we might feel less comfortable with others' perspectives.