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&lt;String&gt; anagrams(String[] original) {


    HashMap&lt;String, ArrayList&lt;String&gt;&gt; map = new HashMap();


    for(String str : original) {

        String key = sortChars(str);

        if(!map.containsKey(key)) {
            map.put(key, new ArrayList&lt;String&gt;());
        }

        ArrayList&lt;String&gt; anagramList = map.get(key);
        anagramList.add(str);
    }

    ArrayList&lt;String&gt; result = new ArrayList();

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

        ArrayList&lt;String&gt; anagramList = map.get(key);

        if(anagramList.size() &gt; 1) {

            result.addAll(anagramList);            
        }
    }

    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&lt;String, List&lt;String&gt;&gt; instead of HashMap&lt;String, ArrayList&lt;String&gt;&gt; (note, use List instead of ArrayList).
The two lines:


ArrayList&lt;String&gt; 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&lt;String&gt; anagramList : map.values()) {
    if (anagramList.size() &gt; 1) {
        result.addAll(anagramList);
    }
}