# Time complexity of anagram solution

I have written code to return anagrams from a list of words. I'm a newbie in time complexity analysis so pardon my ignorance if this is a blatantly obvious question. Am I right in thinking this is in O(n log n) time, since it's just performing a quicksort and the rest is done in O(1) time because it's hashmaps? Also any suggestions on improving the code?

    public class anagram {

public static ArrayList<String> anagrams(String[] original) {

HashMap<String, ArrayList<String>> map = new HashMap();

for(String str : original) {

String key = sortChars(str);

if(!map.containsKey(key)) {
map.put(key, new ArrayList<String>());
}

ArrayList<String> anagramList = map.get(key);
}

ArrayList<String> result = new ArrayList();

for(String key : map.keySet()) {

ArrayList<String> anagramList = map.get(key);

if(anagramList.size() > 1) {

}
}

return result;
}


You are close to right on the complexity. You have two dimensions that are independent in your system though. The sort is sorting the letters in a word, and its performance is dependent on the length of the word, not the number of words.

You have essentially an outer loop which is linear $O(n)$ and an inner sort which is dependent on m, the number of letters in each word...., and those combine to create an overall complexity of $O({n} \times {m}\log{m})$

If you double the average size of each word, the execution time will slightly-more-than-double. If you double the number of words, the same will happen.

Now, how can it be improved?

• your class is called anagram ? It should be capitalized to Anagram.
• you should use the interface declaration not the implementation, where you can. For example, your HashMap should be HashMap<String, List<String>> instead of HashMap<String, ArrayList<String>> (note, use List instead of ArrayList).
• The two lines:

ArrayList<String> anagramList = map.get(key);


could be simplified to:

map.get(key).add(str);

• You iterate through the keys of the HashMap to get the value arrays, but you don't need to. Consider the following (which just iterates the values...):

for (List<String> anagramList : map.values()) {
if (anagramList.size() > 1) {