Replacing string comparisons with dictionary lookups

Question

Given 2 strings s1 and s2, if I do a simple equality check , it is considered to be O(n) when calculating algorithm efficiency. So, if I am using a brute force approach for the rotated substring question the efficiency is O(n^2) (take the 2nd substring, rotate by 1 and check. Repeat till rotations = strlen or matched)

However, a Dictionary lookup is considered O(1). If I instead used a dictionary with the sole element having a dummy value and a key = s1. Then , instead of doing a string compare I checked for the existence of s2 in the dictionary, wouldnt my complexity go down to O(n)?

Intuitively it doesnt make sense to me, so I'm guessing one of my assumptions is incorrect...

Answer 1

A dictionary also has to do at least one comparison. If the length of the string is the variable of interest, this has to be taken into account and since the comparison is O(strlen) a lookup takes O(strlen) time too. We say hash table lookups (are expected to) take O(1) time regarding the number of entries.

Aside: A hash table with a single key would not solve the rotated substring problem. Doing this once for each rotation still takes O(strlen^2) time in total, since you do O(strlen) comparisons that take O(strlen) time each (see above). You can, however, fill one table with all of the n rotations and then takes a lookup, and under the same assumptions that imply O(1) lookup in terms of the number of keys, this takes O(strlen) time in total. However, it also takes O(strlen^2) space, which is a downside.

The reason this works for a single lookup in a single hash table of all rotations (but not for doing many lookups in single-element hash tables) is that the hashing cheaply distributes the strings in disjoint buckets, so that almost all comparisons are avoided. Strings with different hashes are culled with a hash calculation and array lookup.