4 ms·

1000x is still O(1000N) == N. So technically not significantly faster.

• JoeAltmaier 12y ago
  Except that 'spelling' is a bounded problem. There aren't going to be more words in the dictionary, at least not orders more, any time soon. 'Scaling as the word list grows' is meaningless. So the only definition of 'faster' that matters is the one they used.
  • toolslive 12y ago
    That's a rather "English only" view on the topic. Spelling is not a bounded problem in every language. Some power languages (Dutch, German) have an infinite number of words, as you can take 2 nouns (fe a and b) and concatenate them to form a new one (ab means something else than ba). Some languages also have inflection....
• ghkbrew 12y ago
  That all depends on what you consider a significant speed up. For small values of N constant factors will usually dominate. In this case, they mention that lookup time is independent of dictionary size, so the "N" in question is actually a combination of the word size and the edit distance, both relatively small quantities.