Two algorithms can produce the same result while requiring very different amounts of work as the input grows. Asymptotic complexity describes how resource use scales with input size.

Big-O notation

If the running time grows no faster than a constant multiple of a function $g(n)$ for sufficiently large $n$, it is written

$$T(n)=O(g(n)).$$

Common growth classes include

$$O(1),\quad O(\log n),\quad O(n),\quad O(n\log n),\quad O(n^2).$$

Ignore constants, not reality

Big-O deliberately suppresses constant factors and lower-order terms so that scaling behaviour is visible. It does not say that all algorithms in the same class take equal time on a real machine.

An $O(n)$ algorithm with poor memory locality can be slower than another $O(n)$ algorithm by a large constant factor.

Space complexity

The same notation can describe how additional memory grows with input size.

Worst, average and amortized costs

An operation can have different costs depending on the input and on earlier operations. Data structures are therefore often compared using worst-case, expected or amortized complexity rather than one universal cost.

Complexity provides a machine-independent first comparison; later performance analysis adds the effects of memory layout, caches and actual hardware.