alt Hacker NewsNotable pitfalls:
- s[i:j] is O(j - i) because it creates a copy instead of a view
- max(range(n)) is O(n)
- substring search is O(n), which is good, but rfind is O(n m)
- iterative string concatenation (for c in ...: s += c) can be O(n^2) due to string immutability according to footnote 10, although it is O(n) in most cases due to an implementation detail of CPython: https://stackoverflow.com/a/34008199
Replies
chronial • yesterday at 5:38 PM
Note the footnote for rfind:
> This is the worst case. Reverse searches are O(n) on typical input.
➕ show 1 reply
realloc is frequently O(n), ie CPython can avoid copying and immediately collecting the object but still copy the bytes. It's the same as calling reserve in a loop