I could have used more precise terminology. rfind is average case O(n + m), worst case O(n * m). Imho the worst case performance is more important than the average case performance, since it tells us whether there is any risk for attacks like Hash DoS, which is the reason why Python's dict hashing had to be changed. https://peps.python.org/pep-0456/