Linearithmic function

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Time complexity — In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O… …   Wikipedia

  • Element uniqueness problem — The element uniqueness problem is a fundamental problem in computational complexity theory, being a problem for which a direct proof exists [ [http://ru linux geek.livejournal.com/35523.html A proof I will never forget: An algorithms story] ]… …   Wikipedia

  • Andrew Odlyzko — Born 23 July 1949 Tarnów, Poland Fields Mathematics Instituti …   Wikipedia

  • Big O notation — In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is… …   Wikipedia

  • Binary logarithm — NOTOC In mathematics, the binary logarithm (log2 n ) is the logarithm for base 2. It is the inverse function of n mapsto 2^n. The binary logarithm is often used in computer science and information theory (where it is frequently written lg n , or… …   Wikipedia

  • In-place matrix transposition — In place matrix transposition, also called in situ matrix transposition, is the problem of transposing an N imes M matrix in place in computer memory: ideally with O(1) (bounded) additional storage, or at most with additional storage much less… …   Wikipedia

  • Cooley–Tukey FFT algorithm — The Cooley–Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N1N2 in terms of smaller DFTs… …   Wikipedia

  • Logarithmic growth — In mathematics, logarithmic growth describes a phenomenon that whose size or cost can be described as a logarithm function of some input. e.g. y = C log ( x ). Note that any logarithm base can be used, since one can be converted to another by a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”