2 ms·
Note the footnote for rfind: > This is the worst case. Reverse searches are O(n) on typical input.
by chronial 1mo ago
Note the footnote for rfind:
> This is the worst case. Reverse searches are O(n) on typical input.
- gpugreg 1mo agoI 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/ https://peps.python.org/pep-0456/