Cost, scale & Big O
Predict how work grows, then measure the part that matters.
BY THE END, YOU CAN
- Distinguish asymptotic growth from elapsed time
- Recognize linear, logarithmic, and quadratic work
- Design a fair performance comparison
Diagram description: O(1); O(log n); O(n); O(n²)
Count work before seconds
Big O describes an upper bound on how resource use grows with input size, under stated assumptions.
Scanning every job once takes linear work, written O(n). Comparing every pair performs roughly n squared comparisons, or O(n²). Halving a search region repeatedly takes O(log n) steps.
These descriptions omit constant factors and machine details. They are useful for predicting growth, not for claiming that one implementation is always faster on a tiny input. Define what n represents before using the notation.
Hidden work still counts
A short line can conceal a loop.
Testing membership in a list scans elements; doing it inside another loop may create quadratic work. A set can make expected membership lookup constant time, at the cost of extra memory and hashing (computing a number from each value to find it quickly). Copying a list or slicing (taking a range of) most of it also costs time and space proportional to the number of copied elements.
For Relay, repeatedly reconstructing the entire queue to process one item can dominate the actual job handling even if the source code looks elegant.
Measure a realistic hypothesis
A benchmark should answer a question such as 'does removing the front of this queue dominate processing at one hundred thousand jobs?' Keep input, setup, and environment comparable.
Separate setup from the operation being timed, repeat measurements, and examine more than one input size. Wall-clock time can include waiting; a profiler helps locate where execution time is spent. Optimize after identifying a constraint and retain a readable baseline.
A tenfold speedup in a component that uses one percent of total time has limited impact.
COMMON FAILURE MODE
Treating O(1) as instantaneous or O(n) as slow. Input size, constant factors, memory, and the actual bottleneck still matter.
TRY IT YOURSELF
Estimate comparisons for nested loops over 100, 1,000, and 10,000 jobs. Then explain why multiplying input size by ten can multiply quadratic work by one hundred.
Make the call in the laboratory.
The two-question checkpoint, your notes, and your saved progress are in the laboratory. Free, with no account.
Open in the laboratory ↗CONNECT IT TO RELAY
Compare list front removal with deque removal at several queue sizes. Record the input sizes and limitations of your measurements.