Time complexity: Definition & Examples

Time complexity describes how an algorithm's computational work grows with input size, under a stated cost model. For a quant, it helps answer whether a pair-screening routine that handles a small asset universe will remain practical when that universe expands. It describes growth; it does not predict an exact number of seconds.

Before accepting a complexity claim, identify the input size and the work being counted. Here $n$ will mean the number of assets, and one operation will mean visiting one unordered pair. If each visit instead estimates a correlation from $T$ observations by scanning both series, the pair count alone leaves out a whole input dimension: the total work is then $\Theta(n^2T)$ under constant-cost arithmetic and a constant amount of work per observation.

Count the work before naming its order

Suppose a fictional screening task examines every distinct pair of assets once. Asset A with B is the same pair as B with A, and an asset is never paired with itself. The first asset has $n-1$ later partners, the next has $n-2$ , and so on. The exact number of pair visits is

P(n) = \sum_{i=1}^{n-1}(n-i) = \frac{n(n-1)}{2}.

Four assets require 6 visits; eight require 28. Doubling the universe does not produce exactly four times the work at these small sizes. The quadratic term describes the dominant growth as

n

increases.

Upper-triangular grids show one blue cell per unordered asset pair: four assets give 6 visits and eight give 28. Diagonal cells and the lower triangle are skipped.

One cell per pair visit. These are exact operation counts, not measured runtimes.

This Python example counts the loop body's executions explicitly. It illustrates the work of visiting the pairs; if only the number of pairs is needed, the formula avoids enumerating them.

def count_pair_visits(n: int) -> int:
    """Count one visit per unordered pair of n distinct positions, n >= 0."""
    visits = 0
    for i in range(n):
        for j in range(i + 1, n):
            visits += 1
    return visits

for n in (4, 8):
    print(n, count_pair_visits(n))
# 4 6
# 8 28

The count is exact; it is not a count of every instruction executed by Python. Under the usual model in which index arithmetic, loop steps and increments cost constant time, this routine takes

\Theta(n^2)

time. Python integers have arbitrary precision, so a bit-level analysis must also account for the growing size of indices and the counter. A claim about constant-cost arithmetic is a model assumption, not a promise that every operation on an arbitrarily large Python integer takes the same time. Python numeric types specify that integer precision is unlimited.

An upper bound is different from a tight bound

Big O notation gives an asymptotic upper bound:

P(n)=O(n^2)

means that, beyond some threshold, a fixed constant times

n^2

bounds the count above. A tight bound,

P(n)=\Theta(n^2)

, bounds it both above and below by positive constant multiples of

n^2

For this example, when $n\ge2$ ,

\frac{n^2}{4} \le \frac{n(n-1)}{2} \le \frac{n^2}{2}.

Those inequalities establish the tight quadratic order. The looser statement

P(n)=O(n^3)

is also true, but hides useful information. Neither notation supplies a time unit or an exact runtime. See the NIST definitions of Big O and Theta.

The relevant case must also be stated:

Kind of claim	What is being bounded?
Worst case	The largest cost among valid inputs of the same size.
Average case	Expected cost under a specified input distribution, and any stated algorithmic randomness.
Amortized	Cost spread across a sequence of operations, with a bound on the total even when individual operations can be expensive.

Amortized analysis does not require a probability distribution over inputs; it does not guarantee a cheap individual operation. Cornell's amortized-analysis notes explain this distinction. The displayed pair loop has no data-dependent early exit, so every input universe of size

n

produces the same number of visits.

Streaming changes storage, not the number of pairs

Time and space complexity answer separate questions. If a routine materializes one fixed-size result for every pair, its output alone contains

\Theta(n^2)

records. Processing one pair at a time and discarding its result can avoid retaining that output, while still performing every visit.

The displayed counting loop keeps a constant number of integer variables:

O(1)

auxiliary words under the model above, excluding input and output. Their bit lengths need not be constant. Python's itertools.combinations likewise emits pairs incrementally, but pools its input; for pairs it uses

O(n)

retained input references rather than storing all

\Theta(n^2)

output tuples. Calling list on the iterator materializes those tuples again.

Use complexity to spot scaling problems, then benchmark a concrete implementation on representative data. Constants, memory traffic, the work performed inside each visit and the deployment environment determine the elapsed time.

For a fuller derivation, Algorithms, Growth Rates, and Asymptotic Notation develops case analysis and formal bounds using insertion sort. The public link is a preview; the full lesson requires membership.

Practice

A screening routine consumes every unordered pair of 10 distinct assets, one at a time. It retains no pair results. Does this make its total pair-visiting work linear in the number of assets?

Answer. No. There are

10\times9/2=45

visits. Streaming reduces retained output storage; it does not change the quadratic number of visits when every pair must be examined.

Sources

NIST Dictionary of Algorithms and Data Structures: Big O notation — upper bounds and the dependence on the computation model.
NIST: Theta — the two-sided definition of a tight asymptotic bound.
Cornell CS 3110: Amortized Analysis Examples — sequences of operations versus average-case analysis.
Python 3.14 documentation: combinations — output cardinality, position-based identity and input pooling.
Python 3.14 documentation: numeric types — arbitrary-precision integers. Example executed with Python 3.14.4; the checked documentation served Python 3.14.10.

Count the work before naming its order

An upper bound is different from a tight bound

Streaming changes storage, not the number of pairs

Practice

Sources

Related terms

Space complexity