Growth Rates and Big O

Why we count steps

Timing a program tells you about one machine, one compiler and one input. Change any of them and the number changes. To compare algorithms rather than computers, we count basic operations (a comparison, an addition, an array access) as a function of the input size $n$, and ask how that count grows.

def linear_search(items, target):
    for i, item in enumerate(items):
        if item == target:
            return i
    return -1

If target is absent, the loop makes $n$ comparisons. If it sits at the front, one. When nothing else is said, we analyse the worst case, because it is a guarantee: no input of size $n$ can cost more.

Exact counts are fragile, and whether an iteration is three operations or five does not change the shape of the curve. Asymptotic notation keeps the shape and discards the rest.

The three definitions

Let $f$ and $g$ be functions from the positive integers to the non-negative reals.

Upper bound. $f(n) = O(g(n))$ if there are constants $c > 0$ and $n_0 \ge 1$ such that

Lower bound. $f(n) = \Omega(g(n))$ if there are constants $c > 0$ and $n_0 \ge 1$ such that

Tight bound. $f(n) = \Theta(g(n))$ if both hold, that is, if there are constants $c_1, c_2 > 0$ and $n_0 \ge 1$ such that

Two constants do all the work: $c$ says we do not care about constant factors, and $n_0$ says we do not care about small inputs. The equals sign is a historical abuse of notation. $O(g(n))$ is really a set of functions and $f$ is a member of it, so read it as "is", never as an equation you can turn around.

A worked proof

Claim. $3n^2 + 5n = O(n^2)$.

To prove it we must produce a $c$ and an $n_0$. For every $n \ge 1$ we have $n \le n^2$, so

Choose $c = 8$ and $n_0 = 1$. That is the entire proof.

The witnesses are not unique. For $n \ge 5$ we have $5n \le n^2$, so $c = 4$, $n_0 = 5$ works just as well. A smaller $c$ usually costs a larger $n_0$.

The lower bound is easier. $3n^2 + 5n \ge 3n^2$ for all $n \ge 1$, so $3n^2 + 5n = \Omega(n^2)$ with $c = 3$. Both bounds together give $3n^2 + 5n = \Theta(n^2)$.

Common growth rates

A machine doing a billion steps per second finishes the first six rows in a second or less. It will not finish the last two before the sun burns out. That gap, not a factor of two here or there, is what asymptotic analysis is for.

Common mistakes

1. Reading $O$ as "exactly". $n = O(n^2)$ is true, and useless. $O$ is an upper bound. When you mean a tight bound, say $\Theta$.
2. Confusing the bound with the case. Worst, best and average case choose which function to study. $O$, $\Omega$ and $\Theta$ describe how that function grows. Insertion sort is $\Theta(n^2)$ in the worst case and $\Theta(n)$ in the best, and both statements are tight.
3. Keeping constants. $O(2n + 3)$ is simply $O(n)$. The base of a logarithm disappears the same way, since $\log_a n$ and $\log_b n$ differ only by the constant factor $\log_b a$.
4. Dropping constants from an exponent. That rule does not extend upstairs. $2^{2n} = 4^n$ is not $O(2^n)$.
5. Forgetting $n_0$. An $O(n \log n)$ algorithm can lose to an $O(n^2)$ one on small inputs. This is why real sorting libraries switch to insertion sort for short runs.

Exercises

1. Prove from the definition that $5n + 20 = O(n)$. Give explicit values of $c$ and $n_0$.

2. True or false: (a) $2^{n+1} = O(2^n)$, (b) $2^{2n} = O(2^n)$.

3. How many times does the comparison on the highlighted line run, as a function of $n$? Give a $\Theta$ bound and justify it.

def count_pairs(items):
    n = len(items)
    count = 0
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] == items[j]:
                count += 1
    return count