Linearithmic - Definition and Overview

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

Some famous algorithms that run in linearithmic time include:

• Quicksort on the average case
• The Fast Fourier transform
• Monge array calculation