Objectives#
- Define input size with one or more variables instead of assuming every problem has a single n.
- Distinguish worst-case, expected, and amortized bounds without treating them as interchangeable.
- Account for auxiliary, output, and recursion-stack space separately.
- Derive loop, recurrence, library-operation, and output-sensitive costs from the operations performed.
Start with inputs and the kind of bound#
Write down what can grow. A graph may need V vertices and E edges; comparing two strings may need n and m; returning every pair can make output size k part of the cost. Big-O without these definitions hides the claim being made.
Worst-case bounds cover every valid input of a given size. Expected bounds depend on a stated random process or distribution. Amortized bounds spread the cost of occasional expensive operations across a sequence; they do not mean that each individual operation is cheap.
Check the reasoning
- Can you name every independent input variable in the bound?
- If you say expected or amortized, can you state the expectation or operation sequence that justifies it?
Count progress, not indentation#
Nested loops are not automatically quadratic. If two pointers only advance and neither retreats, there are at most n moves by each pointer: at most 2n pointer advances, so the scan is O(n). The proof is the monotone progress measure, not the visual nesting.
For recursion, write the work outside the recursive calls and the sizes of the subproblems. A recurrence such as T(n)=2T(n/2)+O(n) describes two half-size calls plus a linear combine step; T(n)=T(n-1)+O(1) describes a single chain. Stack depth must be counted separately from total calls.
Check the reasoning
- What quantity strictly advances or shrinks on every iteration or recursive edge?
- How many times can one input item be visited, inserted, removed, copied, or compared?
Include library, copying, and output costs#
A queue loop is only linear when removing the front has the claimed cost. Repeatedly shifting an array-backed sequence can move the remaining elements each time, producing quadratic total work. A deque or an array plus a head index avoids that repeated movement; occasional compaction can still be amortized linear over the sequence.
A copied substring of length k takes O(k) time and O(k) new space under a copying string model, even if the source indices were found in O(1). Producing q such strings costs at least the total number of output characters. State the actual language/runtime contract rather than borrowing an operation cost from another language.
Check the reasoning
- Does a library call scan, shift, sort, hash, compare, or allocate behind the name you wrote?
- Would the algorithm still have the claimed bound after including copied output and returned collections?
Separate the kinds of space#
Auxiliary space is temporary working memory beyond the input and required output. Output space is the result itself. Recursive code also consumes one call frame per active depth unless the environment guarantees an optimization. Report these separately when doing so changes the reader's understanding.
Check the reasoning
- Is a result collection required output or temporary working state?
- What is the maximum number of simultaneously active call frames?
Worked example: Why the queue representation changes the bound#
Process [A, B, C, D] in FIFO order. Contrast deleting index 0 after every visit with keeping a head index over the same array.
| Step | State | Why it matters |
|---|---|---|
| Front deletion 1 | visit A; shift B, C, D | Three live elements move left after the first deletion. |
| Front deletion 2 | visit B; shift C, D | Two more elements move; the repeated work depends on the remaining length. |
| Front deletion total | 3 + 2 + 1 + 0 moves | For n elements the sum is n(n-1)/2, so the queue loop is O(n²) under this operation contract. |
| Head-index pass | head: 0 → 1 → 2 → 3 → 4 | Each visit increments head once and does not shift the tail, so the pass is O(n). |
| Optional compaction | copy the remaining suffix occasionally | If compaction only follows enough consumed entries, each entry is copied a bounded number of times and the sequence remains O(n) amortized. |
Conclusion: The loop body looked constant in both versions, but the front-removal contract hid repeated movement. Complexity belongs to the implementation and operation semantics, not to the data-structure label alone.
Misconception to correct#
Two nested while loops always make an algorithm O(n²).
Count state transitions. When left and right each advance at most n times across the whole run, their nested-looking scan is O(n), assuming the body is O(1).
Short exercise#
A routine advances right from 0 to n-1 and advances left only forward, never past right. On each step it returns a newly copied substring input[left:right+1]. What are the scan cost and the total cost including copies?
Reveal the worked answer
The pointer advances are O(n) because each pointer moves at most n times. The substring copies add O(K) time and output space, where K is the total number of characters copied across all returned substrings. The complete bound is O(n + K) time and O(K) output space, plus O(1) auxiliary pointer state.
Put it into practice#
Choose one BFS/queue problem and one two-pointer problem. Before coding, write the language-specific cost of every queue removal and the maximum number of moves by each pointer.
Practice queue and pointer cost claims