Anagram algorithm with minimum complexity

Question

I recently was asked to design an algorithm that checks if two strings are anagrams of one another. My goal was to minimize space and time complexity, so I came up with this algorithm:

1. Create an array of 26 elements, each initialized to zero.
2. Traverse the first string and for each character, increment the array element corresponding to that character.
3. Traverse the second string and for each character, decrement the array element corresponding to that character.
4. Scan over the array. If all elements are 0, the two strings are anagrams.

However, the time complexity of this algorithm is O(n) and I cannot come up with an algorithm with lower complexity. Does anybody know of one?

Answer 1

Your algorithm is asymptotically optimal. It's not possible to solve this problem in any better than Ω(n) time. To see this, suppose that an algorithm A exists that can solve the problem in o(n) time (note that this is little-o of n here). Then for any 1 > ε > 0, there is some n such that for any input of size at least n, the algorithm must terminate in at most εn steps. Set ε = 1/3 and consider any inputs to the algorithm that are of length at least n for the aforementioned n for this ε. Since the algorithm can look at most 1/3 of the characters in the two strings, then there must be two different inputs to the function, one that is a pair of anagrams and one that isn't, such that the algorithm looks at the same subset of the characters of each input. The function would then have to produce the same output in each case, and thus would be wrong on at least one of the inputs. We've reached a contradiction, so no such algorithm must exist.