Linear time

Linear time

An algorithm is said to take linear time, or ${\displaystyle O(n)}$ time, if its time complexity is ${\displaystyle O(n)}$. Informally, this means that the running time increases at most linearly with the size of the input. More precisely, this means that there is a constant ${\displaystyle c}$ such that the running time is at most ${\displaystyle cn}$ for every input of size ${\displaystyle n}$. For example, a procedure that adds up all elements of a list requires time proportional to the length of the list, if the adding time is constant, or, at least, bounded by a constant.