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);
      }
  }