Time complexity of anagram solution

Question

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);
 anagramList.add(str);
 }
 ArrayList<String> result = new ArrayList();
 for(String key : map.keySet()) {
 ArrayList<String> anagramList = map.get(key);
 if(anagramList.size() > 1) {
 result.addAll(anagramList); 
 }
 }
 return result;
}

Answer 1

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);
  anagramList.add(str);
  

  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) {
   result.addAll(anagramList);
   }
  }
  

• B.oof: Thanks so much for clarifying that for me. You've been really helpful :)