How to find space complexity for anagram question

user_18513992 0
Viewed 53

I use two 26 element arrays in my program.
What is the time and space complexity for this program to find if a string is an anagram of another?

int arr1[26] = { 0 };
int arr2[26] = { 0 };

for (char& x : s)
arr1[x - 'a']++;

for (char& x : t)
arr2[x - 'a']++;

for (int i = 0; i < 26; i++) {
    if (arr1[i] != arr2[i])
        return false;
}
return true;
anagram space-complexity time-complexity arrays c++
1 Answers

In the answer below I assume n is the total length of the input, i.e. s.length() + t.length().

Space complexity:
You require 2 arrays of 26 elements (ints in this case).
Since this is a constant that does not depend on the input size, the space complexity is O(1).

This is of course in addition to the space required to store the input itself (O(n) assuming it is all in memory).

Time complexity:
The first 2 loops will traverse the input once. For each element you do a constant number of operations (incrementing a counter in an array). Therefore their time will be O(n).
The last loop has a constant time that does not depend on the input size (26 iterations). Therefore it is O(1).
Together the time complexity is O(n).

user_185199210
Related