All courses › Intermediate Programming › Time complexity, O-notation

Time complexity, O-notation

O-notation describes how an algorithm's running time grows with the number of elements $n$ , for large $n$ . $O(1)$ is constant, $O(\log n)$ grows slowly, $O(n)$ linearly and $O(n^2)$ quadratically. This is what determines whether an algorithm can handle large amounts of data.

O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2)

typical order, fastest to slowest

Symbols

n

number of elements

Example

Lookup in a dict is $O(1)$ : almost independent of size.

Binary search in a sorted list is $O(\log n)$ : the search space halves each step.

Doubling

n

in an

O(n^2)

algorithm quadruples the running time — not just doubles it.

Practise algorithms and data structures for free →

← @property · Recursion →

Part of Intermediate Programming: Algorithms and data structures.