Linear time
From Wikipedia, the free encyclopedia
In computational complexity theory, an algorithm is said to take linear time, or O(n) time, if the time it requires is proportional to the size of the input, which is usually denoted n. Put another way, 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. Technically, it's only necessary that for large enough n, the algorithm takes more than ''an'' time and less than bn time for some positive real constants a and b. 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 the standard computation model are able to run in linear time. There are several hardware technologies which exploit parallelism to provide this. An example is content-addressable memory.
For a given sorting algorithm, for example, it can be proven that there exists an order of elements over which this sorting algorithm will execute in linear time. However, for the general case, sorting algorithms which are based on comparing elements can not perform better than O(n log(n)). Such a proof of lower bound complexity is covered by omega notation; a generalized sorting algorithm is said to be of Ω(n log(n)). Likewise, it can be shown that finding the maximum of a set of unordered elements is Ω(n), as logically one has to perform at least (n-1) comparisons to ascertain the largest element.
Any problem whose result depends on the full input (which is the case for most interesting problems) will require at least linear time to solve, since it takes linear time to read the input.
