Time complexity

Summary

The time complexity of an algorithm is the number of elementary steps it takes, as a function of the length of its input. Usually one takes the worst case over all inputs of a given length. It is stated up to constant factors with big O notation, such as $O(n)$, $O(n \log n)$ or $O(2^n)$. The time complexity of a problem is that of the fastest algorithm solving it, and it defines classes such as $\mathrm{DTIME}(f(n))$ and P. Time is the main resource studied in computational complexity theory.