O(n * log n) describes an algorithm whose operation count grows with the input size multiplied by its logarithm. It grows faster than O(log n) or O(n), but much slower than O(n²) as inputs become large. section 1.10 section 4.3
Use these familiar algorithms to place the bound on the performance scale:
- Merge sort runs in O(n log n) every time. section 4.3
- Quicksort averages O(n log n) when its pivots divide the array reasonably, but can reach O(n²) in the worst case. section 4.5
- Selection sort is O(n²), making it slower for large inputs than an O(n log n) sorting algorithm. section 4.3
Why quicksort can take O(n log n)
At one level of quicksort, partitioning touches all n elements, so that level costs O(n). If the partitions stay balanced, the call stack has O(log n) levels. Multiplying the work per level by the number of levels gives O(n) * O(log n) = O(n log n). Random pivot selection produces this running time on average, except for cases such as an array containing only identical elements. section 4.5
Estimates based on a slow computer that performs 10 operations per second
Use the run-time estimates to compare how O(n log n) grows against logarithmic, linear, quadratic, and factorial bounds. section 4.3
