Science Fair Project Encyclopedia
Linearithmic
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(n2), 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
09-23-2007 01:00:40
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details