Linearithmic function

In computer science, a linearithmic function (portmanteau of linear and logarithmic) is a function of the form n · log n (i.e., a product of a linear and a logarithmic term).

In terms of complexity, linearithmic is ω(n), o(n²), and Θ(n · log n). Thus, a linearithmic term grows faster than a linear term but slower than a quadratic term.

In many cases, the n · log n running time is simply the result of performing a Θ(log n) operation n times. 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 linearithmic time.

Comparison sorts require at least linearithmic number of comparisons in the worst case, due to the fact that log(n!) = Θ(n log n). They also frequently arise from the recurrence relation T(n) = 2 T(n / 2) + O(n).

Some famous algorithms that run in linearithmic time include:

• Quicksort on the average case
• Heapsort, merge sort, introsort, binary tree sort, smoothsort, comb sort, patience sorting, etc. in the worst case
• Fast Fourier transforms
• Monge array calculation