Linearithmic
From Wikipedia, the free encyclopedia.

In computer science, a linearithmic function is a function of the form n log n, a product of a linear and logarithmic term.

In terms of complexity, linearithmic is ω(n), O(n²) and Θ(nlogn), or in other words, linearithmic grows faster than a linear term, and slower than a quadratic term.

Some famous algorithms that are in linearithmic time include:

• Average time quicksort
• The fast Fourier transform
• Monge array calculation

The original article can be found at: http://en.wikipedia.org/wiki/Linearithmic.
All text is available under the terms of the GNU Free Documentation License.