log-linear time

Work that grows as n times log n, written O(n log n), the typical cost of efficient comparison sorting.

In more detail

Merge sort, heap sort and the average case of quicksort are log-linear: roughly log n rounds of work, each touching all n items. Any sort that only compares pairs of items needs at least this much work in the worst case. A pattern of "sort, then make one pass" is also O(n log n) overall.

Related terms

Taught in

References