Linearithmic function

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (April 2007) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

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(n^1+ε) 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