Anagrams and complexity

Hello everybody,

          In class this week we discussed complexity of an algorithm. We looked at two different approaches to find all the anagrams of an English word. The first algorithm involved finding all the permutations of the given word then returning all the words in the English word list that match one of the permutations. The second algorithm involved computing the signature of the word - a signature is the alphabetical arrangement of the letters in a word - then iterating through the word list and checking if the signature of our word matched the signature of the word in the word list. This approach was much more efficient then the first approach. The permutation approach involved a ridiculous amount of computations on the given word, followed by a full iteration through the word list for however many permutations were created by our word. As words get larger, the amount of permutations they have grow at a high order. Thus, the number of steps taken for this algorithm grows non-linearly for two inputs -  the length of the word, and the length of the word list. On the contrast, the number of steps taken with the second algorithm grows linearly, as a function of the length of the word list.

         The second algorithm was very clever, and showed that our understanding of a specific problem is key to coming up with a plausible solution. The second algorithm seemed much easier to implement as computer program, compared to first algorithm. However the signature approach involved a stronger intuition of english words.