The goal is to find the first recurring character in a string.
Presented in the video below are two algorithms, the first naive one has time complexity n squared. The second algorithm (starting at 2:34 in the video) runs in O(n). But I don't see why, as each new char needs to be compared to all previous chars in the table, which will lead to a total runtime of n squared again. Maybe here the assumptions about the hardware (Turing machine) are important?
https://www.youtube.com/watch?v=GJdiM-muYqc
CodePudding user response：
But I don't see why, as each new char needs to be compared to all previous chars in the table
The trick is to compare a character to all characters that you have seen in time that is not linear in the number of characters that you've examined. There are multiple ways of doing it, such as using a hash table or a balanced tree. Hash set lookup yields constant time, while a balanced tree lookup yields a log2n time.
To illustrate this point, consider a string consisting only of digits. There are ten possible digits, so the test for "have I seen this digit before" takes at most ten steps, even if you have examined a string of a million digits. The same thing can be done with all characters.
Hash tables take this even further, because they drop the requirement for the number of possibilities to be bounded by something relatively small. Same goes for balanced trees, although the lookup becomes logarithmic.
CodePudding user response：
I got the answer. The reason is the finite number of possible characters. So the comparison will always only take a constant amount of time.