Linearithmic function

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