time complexity

A description of how the amount of work an algorithm does grows as its input gets bigger.

In more detail

Time complexity counts basic steps, such as comparisons or loop iterations, as a function of the input size n. It ignores the speed of the particular machine, because once two algorithms grow at different rates, the slower-growing one always wins for large enough input. It is usually written in Big O notation, such as O(n) or O(log n).

Example

Scanning a list of ten thousand users is O(n); looking one up in a dict is O(1).

Related terms

Taught in

References