Worst-case performance
Worst-case performance is the maximum resource usage or computational cost an algorithm or system can incur over inputs or conditions of a specified size or scope.
Fabulous Adventures in Data Structures and Algorithms
Worst-case performance is the resource usage or execution behavior of an algorithm or data structure on its least favorable inputs.
- How it is used
- Uses worst-case bounds to identify costly operations and compare them with amortized or typical performance.
- How deep it goes
- Works through operation-level time and space arguments, including repeated costs under undo; defers deeper mitigation of persistent-data-structure worst cases.
- Examples
- Compares stack reversal in an immutable queue, repeated dequeue after undo, and nested calls in a recursive permutation generator.
- What you can do after
- Evaluate/understand it by locating expensive operations, stating their resource bounds, and checking whether common or repeated calls change the practical trade-off.
Read how Fabulous Adventures in Data Structures and Algorithms explains worst-case performance →
Practices of the Python Pro
Worst-case complexity is the maximum resource requirement an algorithm can incur over inputs of a given size.
- How it is used
- Compares algorithms for the same task by examining their maximum resource requirements as inputs grow.
- How deep it goes
- Defines Big O and demonstrates O(n²) with nested loops, while also mentioning best-case and average-case analysis.
- Examples
- Uses a Python duplicate checker whose runtime varies according to where matching items appear.
- What you can do after
- Evaluate same-task algorithms by estimating their worst-case growth and spotting nested loops that produce O(n²).
Read how Practices of the Python Pro explains worst-case performance →
Grokking Algorithms, Second Edition
The worst-case scenario is the execution situation in which an algorithm requires its maximum runtime for inputs of a specified size.
- How it is used
- Uses Big O notation to guarantee an algorithm’s maximum runtime for inputs of a specified size.
- How deep it goes
- Explains best, average, and worst cases, then derives quicksort’s O(n²) and O(n log n) bounds from call-stack levels.
- Examples
- Uses phone-book search and quicksort with sorted, balanced, random-pivot, and equal-element inputs.
- What you can do after
- Evaluate algorithms by their maximum runtime and distinguish worst-case behavior from best-case and average-case behavior.
Read how Grokking Algorithms, Second Edition explains worst-case performance →
Related concepts
- performancemeasured by · Performance is the measurable effectiveness or operational behavior of a system under specified conditions, assessed through relevant qualities such as task results, speed, responsiveness, throughput, or resource use.
- average-case analysiscontrasts with · Average-case analysis evaluates an algorithm's expected resource requirements over a specified distribution of inputs of a given size.
- similarity searchmeasures · Similarity search is a retrieval technique that finds or ranks items by comparing their representations with a query according to a similarity or distance measure.
- residual erroruses · Residual error is the difference between an observed value and its corresponding value predicted or fitted by a model.
- change ringing algorithmmeasured by · A change ringing algorithm generates every permutation of distinct elements so that successive permutations differ by one swap of consecutive elements.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.