QuickSort Time Complexity (Big-O)
QuickSort runs in O(n log n) average time and O(n²) worst case, using O(log n) space. It is a divide-and-conquer comparison sort that picks a pivot and partitions in place; the randomized version gives O(n log n) expected time.
Open the interactive DevRef Hub tool →Key facts
| Best | O(n log n) |
|---|---|
| Average | O(n log n) |
| Worst | O(n²) |
| Space | O(log n) |
Frequently asked questions
What is the time complexity of QuickSort?
O(n log n) average, O(n²) worst case.
When does QuickSort hit O(n²)?
On already-sorted input with a tail (last-element) pivot.
Related pages
Big-O of QuickSort is part of DevRef Hub on GOAT Lab — a free reference you can use without signing up, and it works offline. Open the tool above for any custom value.
Part of GOAT Lab — 26 free, browser-based science, engineering and developer tools. No sign-up.