Unscrambling Scrambled Words

[conipto]

This and a PDA would make you own at Scrabble.

Bill

[sql_lall]

O(n) means that if you have n words, you'll have some constant factor * n things you have to check. O(log n) means that if you have n words, you'll have some constant factor * log(n) things to check. If you have a dictionary with 1,000,000 words, O(n) means about 1 million checks, whereas O(log n) is around 20

O(log n) is possible if you apply the algorithm of *Binary Search* to scan through a sorted list. So long as it is sorted (i.e. don't even need to take length into account, just use any consistent sort), you can binary search for an O(log n) retrieval.
Yes, there are other optimisations - one good one would be a weighted binary search. I.e. once the letters are sorted, more will start with 'a' than with 'b', and more with 'b' than with 'c' etc..., so you can speed up your binary search a tiny bit, but it'll only be the difference between 20 operations and about 16 or 17, so possibly not worth it. The key is not looking through every entry in the dictionary.

wossname's hash is simply a numerical method of the above procedure. Instead of using identifying strings, you use floating-point numbers. This'll be slightly faster because:
a) You don't have to sort the letters of each word, and
b) You're dealing with a single number, not a (longer) string
Again, once you get the real number hashes, you sort them and use binary search for retrieval.
The downsides (there are always some) are:
a) Floating point numbers in computers are limited by precision.
b) It's not a perfect hash (I don't think, not with computer constraints on the numbers) although the collisions will be extremely infrequent, if at all.
c) You can't use a weighted binary search as easily.