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 th

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!