Time complexity

An algorithm is a sequence of instructions for solving a problem. Suppose we have a list of numbers and want to find a particular one. Linear search starts at the first item, compares it with our target, then moves to the next item if they differ.

Let $n$ be the number of items: the input size. Here one piece of work is one comparison with an item. Let $T(n)$ denote the number of these comparisons. We are counting work, not elapsed seconds.

Choose the last element. With 5 items, we compare 5 times; with 10 items, 10 times. If there are n items, finding the last one—or confirming that a target is absent—requires n comparisons. This is the worst case: the most work needed among inputs of the same size.

This growth is linear: doubling the list doubles the worst-case comparison count. We describe that bound as O(n), read “big O of n”. The expression inside O tells us a growth scale. It is not the name of a particular algorithm.

A for loop repeats a block of instructions. Now let the outer loop repeat n times. Inside each repetition, another loop repeats n times. Watch the inner loop finish a whole row before the outer loop moves to the next row.

for i = 0 … n−1: for j = 0 … n−1: mark(i, j)

We assumed that marking one square takes a fixed amount of work, independent of n. There are n rows with n squares each. Doubling n doubles both dimensions, so the body runs four times as often. This is quadratic growth. Checks and increments add work, but do not change the quadratic leading growth.

It can, if the array is already sorted from small to large and we can access its middle directly. Compare the middle value with the target. If it is too small, every value to its left is also too small. Discard that part. If it is too large, discard the right part. Repeat with the remaining interval. This is binary search.

To see the growth, first use an ideal halving calculation. After one halving, about $n/2$ candidates remain; after two, about $n/4$. If $c$ is the number of halvings needed to reach one candidate, then:

The logarithm answers a question: “2 raised to which power gives n?” For 8 candidates, 8 → 4 → 2 → 1 gives three ideal halvings, because 2³ = 8. Doubling the input adds only one halving. That is much slower growth in work than checking twice as many items.

Of course not. Return to linear search and choose the first item: one comparison finds it, whatever the list length. Its best case is O(1), meaning bounded work independent of n. A middle target and an absent target can require very different amounts of work on equally long lists.

Suppose a family of inputs always makes the search stop 12 items before the end. For n > 12, the count is n − 12. Those 12 saved comparisons are fixed; when n grows, the n term is what grows. We therefore simplify its growth description to O(n). Writing O(n − 12) describes the same asymptotic class here, but hides the simple linear pattern.

Time complexity describes how the work of an algorithm grows with input size. Big O gives an eventual upper bound on that growth, up to a fixed multiplier. It does not by itself mean “worst case”: we chose worst-case work for our search comparisons. We should always say which case and which operation we are counting.

Here $C>0$ is a fixed multiplier and $n_0$ is a fixed starting size; neither changes with n. The function g(n) supplies the growth scale. An upper bound need not be the closest one: linear work is also bounded by a quadratic function eventually, but O(n) describes it more informatively.

For a polynomial work count with fixed coefficients, the highest power eventually dominates the lower powers. We can check this without guessing. Suppose the count is 3n² + 5n + 12. When n ≥ 1, n ≤ n² and 1 ≤ n², so:

The multiplier 20 stays fixed, so the count is O(n²). This is the same leading-growth idea explored in Limits: relative growth. Exponential, power, root, and logarithmic expressions grow at different rates. We compare their eventual growth, not just the steepness of a short piece of graph.