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
- merge sort — A divide-and-conquer sort that splits the list in half, sorts each half recursively and then merges the two sorted halves.
- comparison sort lower bound — The proven fact that any sort that only compares pairs must make at least about n log n comparisons in the worst case.
- growth rate — The rule that says how fast an algorithm's cost rises as the input size n rises, such as constant, linear or quadratic.
Taught in
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Counting And Radix Sort: Beating N Log N — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers