Comment by hugh
18 years ago
Isn't alphabetically sorting a document containing (potentially) tens of thousands of words going to be pretty slow on a machine of this vintage? Isn't it a bit perverse to have a spellcheck which scales worse than O(N)?
18 years ago
Isn't alphabetically sorting a document containing (potentially) tens of thousands of words going to be pretty slow on a machine of this vintage? Isn't it a bit perverse to have a spellcheck which scales worse than O(N)?
Typical clock rates at that time would have been 5MHz. So let's say you have a 64KB document containing 16K words. For a merge sort that's 2^18 comparisons, each requiring a small number of CPU instructions, so it would take on the order of a quarter of a second. That's better than MS Word running on a modern system :-). Besides, no matter what you do, the bottleneck is going to be reading the dictionary off the floppy.