Linearithmic

From Free net encyclopedia

Revision as of 00:01, 24 January 2006 Pakaran (Talk | contribs) stronger claim ← Previous diff

Current revision Pakaran (Talk | contribs) stronger claim

---

Current revision

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.

Some famous algorithms that run in linearithmic time include:

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