A text pass copies the rest of a large document with a slice each iteration — why does throughput collapse?
answer
- what does the expression have to build?
- a copy costs time proportional to its length
- the suffix shrinks by one each iteration
- suffix lengths sum to a quadratic
- carry offsets instead of materialising values
basics
~20 sA slice that copies costs time proportional to its length, so taking the remaining suffix on every iteration copies a quadratic total of characters — O(n^2) time and allocation. Passing start and end offsets instead keeps the pass linear.
solid answer
~50 sThe loop looks linear because each iteration advances one position, but the slice in the body is not a constant-cost expression: where slicing copies, it costs O(k) for a k-character result, and here k is the whole remaining document. Summing the suffix lengths gives a triangular series, so an O(n) scan becomes O(n^2) time plus O(n^2) bytes of allocation and copying — which is why the symptom is not a gentle slowdown but a collapse that tracks document size superlinearly, with garbage-collection or allocator pressure alongside it. The fix is to stop materialising: carry `(start, end)` index pairs, or a view type that borrows the original storage, and only copy at the boundary where a caller genuinely needs an independent value. Diagnose it by plotting runtime against document length — a straight line means linear, a curve that quadruples when you double the input means you are copying.
go deeper
Remember that producing a k-element copy costs O(k), so a slice inside a loop is not free. If the copy grows with the input, the loop that looks linear is really quadratic.
Explain the triangular sum over shrinking suffixes and give both costs — O(n^2) time and O(n^2) bytes copied at O(n) peak — then show the offset-based rewrite that makes the pass O(n) time and O(1) auxiliary space.
Demonstrate the diagnosis: measure at n, 2n and 4n to show a quadratic curve, attribute the profile to allocation and copying, and know that whether a slice copies or borrows differs by runtime so the habit must be verified, not assumed.
Own the systemic version: input sizes are set by customers, so make the growth assumption explicit with a size guardrail and a scaling test in the pipeline, and decide where in the layering copying is allowed so views never leak and pin large buffers.
## The scene A text-processing pass walks a large document — a several-megabyte technical manual — splitting it into segments. Per iteration it wants "the rest of the document from here", so it writes the obvious thing: ``` i = 0 while i < length(text): rest = text[i .. length(text)-1] // materialises a copy j = index_of_delimiter(rest) if j == -1: break emit(rest[0 .. j-1]) i = i + j + 1 ``` One pointer moving forward, one pass, obviously linear. Except the slice on line 3. ## A slice is a loop wearing a bracket Where a slice **copies**, producing a `k`-element result costs O(k) time and O(k) space: the runtime allocates a buffer and copies `k` units into it. That is a loop, spelled as punctuation. Substituting the loop back in makes the analysis routine. The suffix at position `i` has length `n - i`. Over a scan that advances through the document, the copied volume is: `n + (n-1) + (n-2) + ... + 1 = n(n+1)/2` So the pass is **O(n^2)** in time — and, unusually, also O(n^2) in *allocated bytes over the lifetime of the loop*, even though peak live memory stays O(n) because each copy dies when the next is made. That second number is why the failure feels worse than a plain quadratic loop: you are not only spending processor time, you are pushing megabytes per iteration through the allocator, evicting useful data from cache and giving the memory manager continuous work. ## Why it hides so well Three reasons this survives review and testing: 1. **The fixtures are small.** A 2 KB test document makes the quadratic term invisible; the bug is a property of scale, not of correctness. Output is perfectly right. 2. **The expression reads as free.** Indexing a single character *is* O(1), and slice syntax looks like indexing with an extra bound, so the eye files it under "cheap". 3. **Runtimes disagree, so habits transfer badly.** This is one of the places where mainstream ecosystems made genuinely different calls: a slice expression in Go yields a view sharing the backing array, so it is O(1), while Java's substring has copied since the Java 7 updates that removed shared-offset strings, so it is O(k). An engineer whose instincts formed in one of those is reliably wrong in the other. The portable discipline is to *know which one you are in* and never assume. ## Diagnosing it in production The symptom reported is rarely "quadratic". It is "large documents time out", "the batch window slipped when a customer uploaded bigger files", or "memory pressure spikes during ingest". The confirming measurement is cheap and decisive: run the same code over inputs of size n, 2n and 4n and plot the times. Linear work doubles when the input doubles; copying work quadruples. Two data points beyond the baseline settle the argument without a profiler, and a profiler then names the line, showing time inside allocation and bulk copy rather than inside your comparison logic. ## The fix: index arithmetic instead of materialisation Stop making values you only intend to look at. ``` i = 0 while i < length(text): j = index_of_delimiter(text, i) // searches in place from i if j == -1: break emit_range(text, i, j-1) // caller gets bounds, not a copy i = j + 1 ``` Now each character is examined a constant number of times and nothing is copied, so the pass is O(n) time and O(1) auxiliary space. The general rules: - Prefer helpers that take a **start offset** over helpers that require a pre-trimmed input. - Pass **(start, end)** pairs, or a borrowed view type, through internal layers. - Copy exactly once, at the boundary where a value must outlive or be independent of the original — for example when a segment is stored in a long-lived structure. - Be aware of the mirror-image hazard: a view that borrows a huge document keeps the whole document alive. If you retain a few short segments from a large file, copying them at that point is the *correct* call, because it lets the original be released. ## The transferable lesson This leaf's whole subject is that call costs do not vanish because the call is short. For every expression inside a loop, ask what it *produces*: a value that must be built has a cost proportional to its size, and if that size is proportional to the input, you have a hidden nested loop. Reading, comparing and scanning can usually be done in place; producing cannot.
- The runtime's slice is a view over the original storage, not a copy. Is the loop fine then?The time problem disappears — O(1) per slice makes the pass linear — but a new hazard appears: a view keeps the entire underlying document alive for as long as any slice of it is referenced. Retaining a handful of short segments from a large file then pins the whole file in memory, and the correct fix there is a deliberate copy at the point of retention.
- How do you confirm the slice line is the culprit rather than the parsing logic?Run the same input at n, 2n and 4n characters: parsing work doubles with the input while copying work quadruples, so the shape of the curve names the cause before any profiler is opened. Then confirm with a profile showing time in allocation and bulk copy rather than in comparison, and with an allocation counter that scales with the square of document length.
- Would processing the document in fixed-size chunks fix it?It bounds each copy to the chunk size, so the total copied volume becomes O(n · n/chunk) — better by a constant-ish factor but still quadratic in the number of chunks unless the chunk itself is scanned in place. Chunking is a memory-footprint tool; the complexity fix is still to scan with offsets rather than to materialise the remainder.
Reading the rest of a book from page 40 costs nothing extra if you just keep the book open at that page. This code photocopies every remaining page first, then reads one line, then throws the copies away — and does that again from page 41.
saying these in an interview costs you the question
- Treats slicing as constant-cost because it is one expression
- Assumes every runtime's slice shares storage rather than copying
- Blames the parsing logic instead of the allocation volume
- Reports only peak memory and misses the churn per iteration
- Copies a value that will only be read, never retained