Linear time

In computational complexity, an algorithm is said to take linear time, or Θ(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 the 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 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,b. For more information, see the article on Big-O notation.