Quasilinear time

An algorithm is said to run in quasilinear time (also referred to as log-linear time) if T(n) = O(n logk n) for some positive constant k; linearithmic time is the case k = 1. Using soft O notation these algorithms are Õ(n). Quasilinear time algorithms are also O(n1+ε) for every constant ε > 0, and thus run faster than any polynomial time algorithm whose time bound includes a term nc for any c > 1.

Algorithms which run in quasilinear time include:

• In-place merge sort, O(n log2 n)
• Quicksort, O(n log n), in its randomized version, has a running time that is O(n log n) in expectation on the worst-case input. Its non-randomized version has an O(n log n) running time only when considering average case complexity.
• Heapsort, O(n log n), merge sort, introsort, binary tree sort, smoothsort, patience sorting, etc. in the worst case
• Fast Fourier transforms, O(n log n)
• Monge array calculation, O(n log n)

In many cases, the n · log n running time is simply the result of performing a Θ(log n) operation n times (for the notation, see Big O notation § Family of Bachmann–Landau notations). For example, binary tree sort creates a binary tree by inserting each element of the n-sized array one by one. Since the insert operation on a self-balancing binary search tree takes O(log n) time, the entire algorithm takes O(n log n) time.

Comparison sorts require at least Ω(n log n) comparisons in the worst case because log(n!) = Θ(n log n), by Stirling's approximation. They also frequently arise from the recurrence relation T(n) = 2T(n/2) + O(n).