String Operations Complexity¶
The str type is an immutable sequence of Unicode characters. Python strings have been optimized significantly, especially in Python 3.
Complexity Reference¶
| Operation | Time | Space | Notes |
|---|---|---|---|
len() |
O(1) | O(1) | Direct lookup |
access[i] |
O(1) | O(1) | Direct indexing |
in (substring) |
O(n + m) avg | O(1) | Uses Two-Way / fastsearch algorithm in CPython |
s + s (concatenation) |
O(n+m) | O(n+m) | Creates new string |
s * n (repetition) |
O(n*len(s)) | O(n*len(s)) | Creates new string |
slice [::2] |
O(k) | O(k) | k = slice length |
| Search | |||
find(sub) |
O(n + m) avg | O(1) | Uses Two-Way / fastsearch algorithm in CPython |
rfind(sub) |
O(n*m) worst | O(1) | Uses backward Boyer-Moore-Horspool |
index(sub) |
O(n + m) | O(1) | Like find() but raises ValueError if not found |
rindex(sub) |
O(n*m) worst | O(1) | Like rfind() but raises ValueError if not found |
count(sub) |
O(n + m) avg | O(1) | n = string, m = substring |
startswith(prefix) |
O(m) | O(1) | m = prefix length |
endswith(suffix) |
O(m) | O(1) | m = suffix length |
| Replace/Translate | |||
replace(old, new) |
O(n) | O(n) | Single pass |
translate(table) |
O(n) | O(n) | Single pass with table lookup |
maketrans() |
O(k) | O(k) | k = number of mappings; static method |
expandtabs(tabsize) |
O(n) | O(n) | Replace tabs with spaces |
removeprefix(prefix) |
O(n) | O(n) | Returns slice if prefix matches (Python 3.9+) |
removesuffix(suffix) |
O(n) | O(n) | Returns slice if suffix matches (Python 3.9+) |
| Split/Join | |||
split(sep) |
O(n) | O(n) | Single pass |
rsplit(sep) |
O(n) | O(n) | Split from right |
splitlines() |
O(n) | O(n) | Split on line boundaries |
partition(sep) |
O(n) | O(n) | Split into 3-tuple at first sep |
rpartition(sep) |
O(n) | O(n) | Split into 3-tuple at last sep |
join(iterable) |
O(n) | O(n) | n = total output chars |
| Case Conversion | |||
upper() |
O(n) | O(n) | Must process each char |
lower() |
O(n) | O(n) | Must process each char |
capitalize() |
O(n) | O(n) | Uppercase first, lowercase rest |
title() |
O(n) | O(n) | Titlecase words |