Time complexity in practice

Best, average, worst, amortized time, and what Big-O deliberately ignores. · 6 min read

Time complexity is the count of work as input grows. Big-O is the headline version, but real analysis often asks which case and which operation you are measuring.

Best, average, worst

Best case: the luckiest input. Linear search finds the target at index 0 → O(1).
Worst case: the hardest input. Linear search target absent → O(n).
Average case: expected over typical inputs. Searching for a random present item in an array checks about n/2 items → still O(n).

Worked examples

Example 1 — two separate passes:

for x in a: print(x)
for x in a: print(x * 2)

The first loop runs n times and the second loop runs n times, so the total is 2n → O(n).

Example 2 — every pair:

for i in range(n):
    for j in range(n):
        check(i, j)

For each of n choices of i, j runs n times. Total work is n × n = n² → O(n²).

Example 3 — shrinking work:

for i in range(n):
    for j in range(i + 1, n):
        compare(i, j)

The inner loop does (n−1) + (n−2) + ... + 1 = n(n−1)/2 checks → O(n²), even though it is only half the square.

Example 4 — doubling:

i = 1
while i < n:
    i *= 2

The values go 1, 2, 4, 8, .... After k steps, i = 2ᵏ; stop when 2ᵏ ≥ n, so k = log₂ n → O(log n).

Amortized time

Some operations are usually cheap but occasionally expensive. Appending to a dynamic array is a classic example: most appends are O(1), but when capacity fills, the array allocates a bigger block and copies old items.

Occasional expensive work spread over many operations

many appends cost 1 — Most writes land in existing capacity.
resize copies 1, then 2, then 4, then 8 ... items — Each old item is copied only a small number of times across many appends.
1 + 2 + 4 + ... + n < 2n — The total copying over n appends is linear.

Result: O(1) amortized append

Big-O vs real runtime

Big-O ignores constants, hardware, cache locality, language overhead, and input distribution. That is useful for comparing growth, but it is not the whole performance story. For small n, a clean O(n²) algorithm may beat a complicated O(n log n) one. For large n, the growth curve eventually takes over.