undefined | Better HN

0 pointsmypalmike3y ago0 comments

The hash table is O(1) even without your modification. Because there is a fixed dictionary, the length of the longest possible word is known in advance. That provides a constant bounds that does not grow. Let's say the longest word is 25 letters. Your hash computation is O(25) which is equivalent to O(1).

What this means in practice is that there is no polynomial curve for very long words. You don't bother hashing them, so the curve peaks and then flattens.

Obviously a trie is an interesting and possibly faster solution, though the hash has the benefit of being more cache friendly. But the big O analysis presented for this problem is flawed.

0 comments

3 comments · 2 top-level

bolanyo3y ago· 1 in thread

If dictionary lookup is O(1), we could just make a dictionary of all the doubled words? Now the whole problem is O(1)!

pcthrowaway3y ago

But making that is O(n^2) time and space, where n is the size of the dictionary

barrkel3y ago

It depends on what you are counting as 'n'. It's reasonably clear in the discussion that we're talking about operations on individual characters. Calculating the hash of a string of length n is O(n). Look up in the hash table is still O(1), but you need to calculate the hash first, and that's linear in the length of the string (for non-degenerate hash functions).

On these kinds of problems, I like to suggest that we might be thinking about arbitrarily long "words". Get out of the headspace of language dictionaries, look at things more abstractly. Otherwise a lot of big-O analysis becomes degenerate.

Also, don't forget hostile inputs!

j / k navigate · click thread line to collapse