Working with the notation

The equals sign is not equals, a Theta inside a formula means something specific, and two functions need not be comparable at all.

The definitions from the previous lesson are rarely used directly. In practice you combine known results with a handful of rules, and the rules are worth deriving once so that they are not magic. Start with what happens when two costs are added together, which is what happens whenever one phase of an algorithm is followed by another.

Suppose a procedure scans a list once, costing about $n$, and then does something costing about $n^2$. The total is $n + n^2$. Compare that with the larger of the two on its own.

The ratio starts at 2 and falls towards 1. The smaller term never disappears, but its share of the total does. That is the sum rule: a sum of two functions grows exactly like whichever of them is larger.

What the equals sign means here

Writing $f(n) = O(g(n))$ is an abuse of notation that everybody uses. $O(g(n))$ is really a set of functions, namely all the functions bounded above by some constant multiple of $g$ eventually, and the honest statement is $f \in O(g)$. The equals sign is read left to right and means membership.

So $n = O(n^2)$ is a correct sentence and $O(n^2) = n$ is not, in the same way that saying a robin is a bird is correct and saying a bird is a robin is not. Two claims of the form $f = O(h)$ and $g = O(h)$ do not let you conclude $f = g$, however tempting the symbols make it look. If $f(n) = n$ and $g(n) = n^2$ then both are $O(n^2)$ and they are not remotely equal.

Notation standing inside a formula

You will see expressions like $2n^2 + \Theta(n)$. This means: there is some function $h$ with $h = \Theta(n)$ such that the quantity equals $2n^2 + h(n)$. The notation is standing in for a term whose exact form does not matter, only its growth.

When such an expression appears on the right of an equals sign, the meaning is that for every choice of the anonymous function on the left there is some choice on the right making the equation true. That is what makes a chain like $T(n) = 2n^2 + \Theta(n) = \Theta(n^2)$ legitimate to read in one direction only, from left to right.

The rules worth memorising

Here is the sum rule proved, since it is the one used most. Suppose $f = O(h)$ with constants $c_1, n_1$, and $g = O(h)$ with constants $c_2, n_2$. For every $n \ge \max(n_1, n_2)$ both inequalities apply at once, so $f(n) + g(n) \le c_1 h(n) + c_2 h(n) = (c_1 + c_2)h(n)$. Taking $c = c_1 + c_2$ and $n_0 = \max(n_1, n_2)$ shows $f + g = O(h)$. Two constants went in and one came out, which is why adding a constant number of phases never changes the growth.

And here is why constants vanish. If $f(n) = 7n$ then choosing $c_1 = 7$ and $c_2 = 7$ with $n_0 = 1$ gives $7n \le 7n \le 7n$, so $7n = \Theta(n)$. The constant is absorbed into the $c$ that the definition allowed you to pick, which is exactly the point of allowing it.

Transitivity, and why the constants multiply

Transitivity is the rule that lets you take two bounds you already know and join them into a third. It says that if $f = O(g)$ and $g = O(h)$ then $f = O(h)$. Like every rule here it is proved by producing the pair of constants.

Unfold what the two assumptions give you. From $f = O(g)$ there is a $c_1 > 0$ and an $n_1$ with $f(n) \le c_1 g(n)$ for every $n \ge n_1$. From $g = O(h)$ there is a $c_2 > 0$ and an $n_2$ with $g(n) \le c_2 h(n)$ for every $n \ge n_2$. Take $n_0 = \max(n_1, n_2)$, so that beyond $n_0$ both statements are available at the same time.

Now chain them. Multiplying $g(n) \le c_2 h(n)$ through by $c_1$, which is positive and so leaves the direction alone, gives $c_1 g(n) \le c_1 c_2 h(n)$. Put that after the first inequality and you get $f(n) \le c_1 g(n) \le c_1 c_2 h(n)$ for every $n \ge n_0$. The pair $c = c_1 c_2$ and $n_0 = \max(n_1, n_2)$ satisfies the definition, so $f = O(h)$.

With real numbers in it: let $f(n) = 3n + 4$, $g(n) = n$ and $h(n) = n^2$. For $n \ge 4$, $3n + 4 \le 3n + n = 4n$, so $c_1 = 4$ and $n_1 = 4$. For $n \ge 1$, $n \le n^2$, so $c_2 = 1$ and $n_2 = 1$. The rule hands back $c = 4 \times 1 = 4$ and $n_0 = 4$, and at $n = 4$ that reads $16 \le 64$, which holds and keeps holding.

The product rule, and the nested loop it licenses

The product rule is the one every nested-loop analysis leans on. It says that if $f_1 = O(g_1)$ and $f_2 = O(g_2)$, then the product $f_1 f_2 = O(g_1 g_2)$. The proof is built the same way, and it uses the fact that the definition of $O$ requires the functions to be non-negative.

Suppose $f_1(n) \le c_1 g_1(n)$ for every $n \ge n_1$ and $f_2(n) \le c_2 g_2(n)$ for every $n \ge n_2$, and again set $n_0 = \max(n_1, n_2)$ so both hold together. Multiply the first inequality through by $f_2(n)$, which is at least 0, to get $f_1(n) f_2(n) \le c_1 g_1(n) f_2(n)$. Multiplying by a non-negative quantity cannot flip the direction.

Then multiply the second inequality through by $c_1 g_1(n)$, which is also at least 0, to get $c_1 g_1(n) f_2(n) \le c_1 c_2 g_1(n) g_2(n)$. Joining the two lines gives $f_1(n) f_2(n) \le c_1 c_2 g_1(n) g_2(n)$ for every $n \ge n_0$, so $c = c_1 c_2$ and that $n_0$ prove the rule.

Here is the case it exists for. Procedure B in the first lesson had a loop over every reading, and inside it a second loop over every reading. Call $f_1(n)$ the number of times the outer loop runs, which is $n$, and $f_2(n)$ the cost of one full pass of the outer body, which is one complete inner loop and is at most some constant times $n$. Then $f_1 = O(n)$ and $f_2 = O(n)$, and the product rule gives a total of $O(n \cdot n) = O(n^2)$. On the six readings that was 36 comparisons, which is $6^2$.

Comparing two functions in practice

A question like is $n \log_2 n$ bounded above by $n^{1.5}$ is answered by finding the crossing point and then arguing it never uncrosses. The comparison reduces to $\log_2 n$ against $\sqrt{n}$, since both sides carry a factor of $n$.

At $n = 16$ both sides equal 4. Before that the logarithm is briefly ahead, and after it the square root pulls away and never gives the lead back. So $\log_2 n \le \sqrt{n}$ for all $n \ge 16$, and multiplying both sides by $n$ gives $n\log_2 n \le n^{1.5}$ for all $n \ge 16$. With $c = 1$ and $n_0 = 16$ the definition is satisfied and $n\log_2 n = O(n^{1.5})$.

Not everything is comparable

For ordinary numbers, exactly one of $a < b$, $a = b$, $a > b$ holds. Growth rates have no such guarantee. Consider $f(n) = n$ and $g(n) = n^{1 + \sin n}$. The exponent of $g$ swings between 0 and 2 forever, so $g$ is sometimes far below $f$ and sometimes far above it, and no constant multiple ever settles the matter in either direction.

Neither $f = O(g)$ nor $g = O(f)$ is true. This almost never happens to a real running time, but it is why the notation is defined with quantifiers rather than by saying one function is bigger than another.