title: Higher time complexity but still faster
body: <p>I have two functions to check whether two words <code>word1</code> and <code>word2</code> are anagrams or not (note: two words are said to be anagrams if you can rearrange the letters of one of the words to get the other).</p>
  <pre class="lang-py prettyprint-override"><code>def is_anagram(word1, wrod2):
      histogram = {}
      for char in word1:
          histogram[char] = histogram.get(char, 0) + 1
      # Trying to exhaust all the letters in a histogram by second word
      for char in word2:
          histogram[char] = histogram.get(char, 0) - 1
      for vals in histogram.values():
          if vals != 0: return False
      return True
  
  </code></pre>
  <p>Clearly, in the above function 3 loops are running so it has an overall complexity of <em>O(n)</em></p>
  <p>Here is the second implementation:</p>
  <pre class="lang-py prettyprint-override"><code>def is_anagram2(word1, word2):
      sorted_word1 = ''.join(sorted(word1))
      sorted_word2 = ''.join(sorted(word2))
      return sorted_word1 == sorted_word2
  </code></pre>
  <p>The <code>sorted</code> function has a complexity of <em>nlogn</em>, so the complexity of this function should be <em>O(nlogn)</em>.</p>
  <p>But still if you measure the execution time of theses two functions (e.g. through timeit command in ipython), it is found that the <code>is_anagram2</code> function is faster.</p>
  <p>Please explain why...</p>