Linear time

Linear time

In computational complexity theory, an algorithm is said to take linear time, or O("n") time, if the asymptotic upper bound for the time it requires is proportional to the size of the input, which is usually denoted "n".

Informally spoken, the running time increases linearly with the size of the input. For example, a procedure that adds up all elements of a list requires time proportional to the length of the list. This description is slightly inaccurate, since the running time can significantly deviate from a precise proportionality, especially for small values of "n". For more information, see the article on big O notation.

Linear time is often viewed as a desirable attribute for an algorithm. Much research has been invested into creating algorithms exhibiting (nearly) linear time or better. This research includes both software and hardware methods. In the case of hardware, some algorithms which, mathematically speaking, can never achieve linear time with standard computation models are able to run in linear time. There are several hardware technologies which exploit parallelism to provide this. An example is content-addressable memory.

This concept of Linear Time is used in string matching Algorithms such as Bayer-Moore Algorithm, Ukkonen's Algorithm

See also

* Polynomial time
* Exponential time
* Constant time


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Linear Time Code —   (Longitudinal Time Code), LTC …   Universal-Lexikon

  • Linear Time Temporal Logic — Die Computation Tree Logic (kurz CTL) ist eine Temporale Logik, die speziell zur Spezifikation und Verifikation von Computersystemen dient. Meist wird sie auch mit CTL* bezeichnet. CTL bezeichnet dann eine spezielle Teilmenge der CTL* Formeln.… …   Deutsch Wikipedia

  • Time series — Time series: random data plus trend, with best fit line and different smoothings In statistics, signal processing, econometrics and mathematical finance, a time series is a sequence of data points, measured typically at successive times spaced at …   Wikipedia

  • Time-of-flight mass spectrometry — (TOFMS) is a method of mass spectrometry in which ions are accelerated by an electric field of known strength. [Stephens, W. E., [http://link.aps.org/abstract/PR/v69/p674/s2 A Pulsed Mass Spectrometer with Time Dispersion] Phys. Rev. , 1946, 69 …   Wikipedia

  • Linear temporal logic — (LTL) is a modal temporal logic with modalities referring to time. In LTL, one can encode formulae about the future of paths such as that a condition will eventually be true, that a condition will be true until another fact becomes true,… …   Wikipedia

  • Time and the Conways — is a British play written by J. B. Priestley in 1937 illustrating J. W. Dunne s Theory Of Time through the experience of a moneyed Yorkshire family, the Conways, over a period of roughly twenty years from 1919 to 1937. Widely regarded as one of… …   Wikipedia

  • Time Reversal Signal Processing — is a technique for focusing waves. A Time Reversal Mirror (TRM) is a device that can focus waves using the time reversal method. TRMs are also known as time reversal mirror arrays, as they are usually arrays of transducers, but they do not have… …   Wikipedia

  • 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

  • Linear-quadratic-Gaussian control — In control theory, the linear quadratic Gaussian (LQG) control problem is one of the most fundamental optimal control problems. It concerns uncertain linear systems disturbed by additive white Gaussian noise, having incomplete state information… …   Wikipedia

  • Linear system — A linear system is a mathematical model of a system based on the use of a linear operator.Linear systems typically exhibit features and properties that are much simpler than the general, nonlinear case.As a mathematical abstraction or… …   Wikipedia

Share the article and excerpts

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