Linearithmic function
From Wikipedia, the free encyclopedia
 |
This article does not cite any references or sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. (April 2007) |
In computer science, a linearithmic function (portmanteau of linear and logarithmic) is a function 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(n1+ε) for every ε > 0, and Θ(n · log n). Thus, a linearithmic term grows faster than a linear term but slower than a quadratic term.
In many cases, the n · log n running time is simply the result of performing a Θ(log n) operation n times. For example, Binary tree sort creates a Binary tree by inserting each element of the n-sized array one by one. Since the insert operation on a self-balancing binary search tree takes O(log n) time, the entire algorithm takes linearithmic time.
Comparison sorts require at least linearithmic number of comparisons in the worst case because log(n!) = Θ(n log n). They also frequently arise from the recurrence relation T(n) = 2 T(n / 2) + O(n).
Some famous algorithms that run in linearithmic time include:
- Comb sort, on the average and worst case
- Quicksort on the average case
- Heapsort, merge sort, introsort, binary tree sort, smoothsort, comb sort, patience sorting, etc. in the worst case
- Fast Fourier transforms
- Monge array calculation
