Linearithmic function

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

Some famous algorithms that run in linearithmic time include:

• Quicksort on the average case
• Fast Fourier transforms
• Monge array calculation