Linearithmic

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

In terms of Big O notation, linearithmic is ω( n ), O( n 2), 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 (performance) case *The Fast Fourier transform *Monge array calculation