I have written the following algorithm which takes two words (lists of letters) and checks if the two are anagrams of each other.
areAnagrams(L1, L2)
// i.e. an integer array of size 26, with entries initialised at 0
charCount1[26] := {0} // 26 assignments
charCount2[26] := {0} // 26 assignments
for i from 0 to |L1|
charCount1[(char as integer) L1[i]]++ // n operations
for i from 0 to |L2|
charCount2[(char as integer) L2[i]]++ // n operations
for i from 0 to 25
if charCount1[i] != charCount2[i] // 25 comparisons
return false
return true
end
I believe that its time complexity is O(n)
as overall I think that there are approximate 2n + 77
operations/comparisons.
Can I simply just add the number of operations like this?
Well, formally it's O(|L1| + |L2|). However, if you put n = max(|L1|, |L2|), then it's O(n).