Hacker News new | past | comments | ask | show | jobs | submit login

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.




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!


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


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




The deadline for YC's W25 batch is 8pm PT tonight. Go for it!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: