Best, Average, and Worst Case Complexity in Sorting
When you read that Quick Sort is 'O(n log n) average but O(n²) worst case', what does that actually mean? Best, average, and worst case describe how an algorithm behaves on the most favorable, typical, and most hostile inputs. Understanding the distinction is key to choosing the right sort.
The three scenarios
- Best case — the input that lets the algorithm finish with the least work. Insertion Sort's best case is already-sorted data, giving O(n).
- Average case — expected performance over random inputs. This is usually the most representative figure.
- Worst case — the input that forces the most work. Quick Sort's worst case is O(n²) when pivots are pathological.
Why input order matters
Algorithms react very differently to the shape of their input. Insertion Sort loves nearly-sorted data and hates reversed data. Quick Sort thrives on random data but can choke on sorted data with naive pivots. Merge and Heap Sort are immune — they deliver O(n log n) on every input, which is why they are chosen when predictability matters more than raw speed.
Test every case yourself
The visualizer lets you generate sorted, reversed, and random arrays. Run the same algorithm on each and count the operations — you will directly observe the best, average, and worst cases the textbooks describe.
Frequently asked questions
Which case matters most in practice? +
Why is Quick Sort used if its worst case is O(n²)? +
See it in motion
Watch this algorithm and 9 others run step by step in our free interactive visualizer.
▶ Launch Visualiser