Best, Average and Worst Case

The same algorithm can behave differently on different inputs.

Easy

Quick sort: best/average $O(n\log n)$ , worst $O(n^2)$ on bad pivots. Insertion sort: $O(n)$ on already-sorted data.

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)