Linearithmic function

In computer science, a linearithmic function 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).

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