Run it
The same scan written twice — once slicing on every iteration, once carrying indices — timed at three sizes so the quadratic separates from the linear in front of you.
Where it becomes quadratic
The classic failure is slicing inside a loop:
For a string of length n, the copies total n + (n−1) + (n−2) + … = O(n²). On 100,000 characters that is five billion character copies, and it looks like a perfectly ordinary loop.
The fix is to move an index rather than reslicing:
The same trap appears in recursion, which is how it usually reaches production:
O(n²) because each of the n/2 recursive calls copies the string. Passing indices instead keeps it O(n):
| Pattern | Complexity | Fix |
|---|
s = s[1:] in a loop | O(n²) | Move an index |
f(s[1:]) recursively | O(n²) | Pass indices |
s += x in a loop | O(n²) | Build a list, then "".join |
| Slicing to compare prefixes | O(k) per check | s.startswith(prefix) |
| Slicing to test a substring | O(k) per check | x in s |
startswith deserves the emphasis. s[:len(p)] == p allocates a copy before comparing; s.startswith(p) compares in place and short-circuits on the first mismatch. Same result, no allocation.
Copy, not view
Some languages hand you a slice that points into the original buffer, so taking one is O(1). Python does not: s[2:6] allocates a new string object and memcpys four characters into it. The cost is proportional to the slice, not to the original.
You can prove it from the interpreter: the id differs, and mutating is impossible anyway, so there is no aliasing to observe. What you can measure is the time, which is what the editor below does.
Where it actually hurts
One slice costs nothing worth thinking about. The problem is the shape where a slice is taken per iteration — checking every substring, or peeling a character off the front:
while s: first, s = s[0], s[1:]
Each iteration copies the entire remainder, so an O(n) walk becomes O(n²). The same bug appears in recursive solutions that pass s[1:] down: correct, elegant, and quadratic.
What to do instead
Carry indices. Every algorithm on this track that scans text — two pointers, sliding window, KMP — keeps i and j into the original string and never slices inside the loop. Slice once at the end, when you need the answer as a string.
If you genuinely need a zero-copy view over a large buffer, that exists, but only for bytes: memoryview(b) slices in O(1) and shares the underlying memory.
Avoiding the copy entirely
memoryview gives a genuine zero-copy view — over bytes, not str:
This is why binary protocol parsers work on bytes rather than str: slicing a memoryview is O(1) regardless of size. There is no str equivalent, because Unicode strings may use variable-width internal representations, so a character offset is not always a fixed byte offset.
str.find with a start offset searches a region without slicing it:
Compare with s[pos:].find(","), which copies the remainder on every iteration — the same quadratic trap in a less obvious costume.
re module functions accept pos and endpos on compiled patterns, so matching within a region needs no slice either.
io.StringIO for incremental building, and "".join(parts) for assembling many pieces — one allocation instead of n.
How Python stores strings
Since version 3.3, CPython chooses the narrowest representation that fits the string's characters:
| Content | Bytes per character |
|---|
| ASCII / Latin-1 only | 1 |
| Basic Multilingual Plane | 2 |
| Anything above U+FFFF | 4 |
So a 1,000-character ASCII string uses about 1KB plus roughly 50 bytes of header, while one emoji anywhere in it forces 4 bytes per character — the same text becomes four times larger. That occasionally explains a surprising memory measurement.
Consequences worth knowing:
Indexing is O(1) because the width is fixed per string, so the byte offset is a multiplication. len() is O(1) — it returns a stored count of characters, not bytes. Slicing must copy, since a view would need to carry both the buffer and its width, and immutability makes sharing unnecessary in the common cases.
Questions people ask
Is s[:] free? In CPython it returns the same object, because immutability makes copying pointless. Do not build an algorithm on that guarantee.
Is slicing a list the same? Yes for cost — O(k) and a new list — but the copy is shallow: the new list holds the same element references.
Does negative indexing cost more? No. s[-1] is s[len(s)-1], computed arithmetically.
What about out-of-range slices? They clamp silently. "abc"[0:100] is "abc" — no error, unlike indexing.
Is s[::-1] the fastest reversal? Yes for strings; reversed(s) gives a lazy iterator when you do not need the whole reversed string materialised.
How do I slice without copying? Convert to bytes and use memoryview, or work with indices and functions that accept offsets.
Recap in one screen
s[a:b] allocates and copies: O(b − a) in time and memory, not a view.s = s[1:] in a loop, or f(s[1:]) in recursion, is O(n²) — pass indices instead.- Use
startswith, in, and find(sub, pos) rather than slicing to inspect a region. memoryview over bytes gives true O(1) slicing; there is no str equivalent.- CPython stores strings at 1, 2 or 4 bytes per character, so
len and indexing are O(1).