Growth of functions and algorithm complexity

This week is the last topic of the midterm. The question types are fixed and mechanical: “Show that f is O(g), give witnesses”, “show that f is not O(g)”, “arrange in order of growth” and “how many times is this line executed?”. All of them have a template. Golden rules:

1. Big-O is an upper bound. It does not measure seconds; it tells you how the number of steps grows as the input grows.
2. Write both witnesses: $C$ and $k$. If one is missing, marks are missing.
3. Constant factors and small terms do not matter. $5n^2 + 100n$ and $n^2$ are in the same class.
4. A “not O” proof is always done by contradiction. Assume the definition, divide, and reach the conclusion that something unbounded is smaller than a constant.
5. When counting loops, first think about a single round of the outer loop, then add up the rounds.

Definition of Big-O

Let $f$ and $g$ be functions. f(x) is O(g(x)) means:

$\exists\, C, k \;\; \text{such that} \;\; |f(x)| \le C\,|g(x)| \;\; \text{whenever} \;\; x > k.$

The constants $C$ and $k$ are called witnesses. Intuition: after some point ($x > k$), the graph of $f$ never goes above $C$ times $g$. What it does at the start does not matter.

The witness pair is not unique. If one pair works, a larger $C$ or a larger $k$ also works. On the exam you are not asked for the one correct pair, you are asked for a pair that works.

$\Theta$ = both $O$ and $\Omega$. That is why in a $\Theta$ question you write two separate inequalities.

Template for finding witnesses

For polynomials there is a three-line recipe. Example: $f(x) = 4x^2 + 7x + 3$ is $O(x^2)$.

When x > 1 we have x < x^2 and 1 < x^2.
Hence 4x^2 + 7x + 3 <= 4x^2 + 7x^2 + 3x^2 = 14x^2 for x > 1.
So f(x) is O(x^2) with witnesses C = 14 and k = 1.

The trick: when $x > 1$ it is allowed to enlarge the small powers to the highest power, because you are making the expression bigger and the direction of the inequality is preserved. Then add the coefficients: $4 + 7 + 3 = 14$.

PITFALL · The sentence “for x > 1”. If you don’t write for which $x$ the inequality holds, you haven’t stated $k$. In the interval $0 < x < 1$ we have $x > x^2$, so the enlarging trick does not work there; that is exactly why $k = 1$.

Theta: the lower bound is free

$f(n) = 3n^2 + 5n + 2$ is $\Theta(n^2)$:

• Upper bound: for $n > 1$, $3n^2 + 5n + 2 \le 3n^2 + 5n^2 + 2n^2 = 10n^2$, so $C_2 = 10$.
• Lower bound: dropping the positive terms makes the expression smaller: $3n^2 + 5n + 2 \ge 3n^2$, so $C_1 = 3$.

Result: for $n > 1$, $3n^2 \le f(n) \le 10n^2$. Write all three constants ($C_1 = 3$, $C_2 = 10$, $k = 1$) together.

If there is a negative coefficient (like $5n^2 - 3n$), the lower bound is not free. Then you use an inequality like $3n \le n^2$ and enlarge $k$. On the midterm a polynomial with positive coefficients usually appears.

The “not O” proof (contradiction)

To show that a function is not $O(g)$, an example is not enough; you must show that the definition cannot be satisfied with any $C, k$. The template is contradiction. Example: $n^3$ is not $O(7n^2)$.

Proof. Suppose, for contradiction, that n^3 is O(7n^2).
Then there are constants C and k with n^3 <= C * 7n^2 for all n > k.
Dividing both sides by n^2 > 0 gives n <= 7C for all n > k.
But this fails for any integer n > max(k, 7C).
This is a contradiction, so n^3 is not O(7n^2). ∎

In plain words: after the division an absurd result appears, like “the unboundedly growing $n$ is always smaller than the constant $7C$”. Whatever $C$ you choose, $n = 7C + 1$ and beyond break it. For example, for $C = 50$ and $n = 351$: $351^3 > 350 \cdot 351^2$.

TIP · The same template works for exponentials. $4^n$ is not $O(2^n)$: assume $4^n \le C\cdot 2^n$, divide both sides by $2^n$, get $2^n \le C$. $2^n$ is unbounded. Contradiction.

Growth ordering

From small to large, the chain to memorize:

$1 \;<\; \log n \;<\; \sqrt{n} \;<\; n \;<\; n\log n \;<\; n^2 \;<\; n^3 \;<\; 2^n \;<\; 3^n \;<\; n!$

Rules:

• In a sum the fastest-growing term wins: $n^2 + 1000n + \log n$ is $O(n^2)$.
• In a product the bounds are multiplied: $(n^2 + 3)\log n$ is $O(n^2 \log n)$.
• The base of a logarithm does not matter: $\log_2 n = (\log_2 10)\log_{10} n$, only a constant factor.
• Adding a constant to the exponent does not matter, multiplying the exponent does: $2^{n+3} = 8\cdot 2^n$ is $O(2^n)$; but $2^{2n} = 4^n$ is not.
• Every exponential with base greater than 1 eventually overtakes every polynomial: even $(1.1)^n$ overtakes $n^{100}$.

Complexity of algorithms

Time complexity: the number of basic operations (comparisons, additions) the algorithm performs, expressed in terms of the input size $n$. Usually the worst case is asked: at most how many operations, however bad the input is.

Examples: linear search for a number that is not in a list of 50 elements takes 50 comparisons. Binary search on a sorted list of 1024 elements (until the interval shrinks to 1 element) goes $1024 \to 512 \to \dots \to 1$, that is 10 rounds. Bubble sort on a reverse-sorted list of 10 elements makes $9 + 8 + \dots + 1 = 45$ comparisons.

Counting loops: step by step

for i := 1 to n
    for j := i to n
        x := x + 1

First think about a single outer round: with $i$ fixed, $j$ goes from $i$ to $n$, that is $n - i + 1$ rounds.

i = 1  ->  n rounds
i = 2  ->  n - 1 rounds
...
i = n  ->  1 round
Total: n + (n-1) + ... + 1 = n(n+1)/2

For $n = 8$, $\frac{8 \cdot 9}{2} = 36$. Big-O estimate: $\frac{n(n+1)}{2} = \frac{1}{2}n^2 + \frac{1}{2}n \le n^2$ ($n \ge 1$), that is $O(n^2)$. Even if it is half of $n^2$, the class is $n^2$.

If the loop variable grows by multiplication ($i := 2i$), the number of rounds is logarithmic. If it shrinks by division ($i := \lfloor i/2 \rfloor$), it is again logarithmic.

Common mistakes

for i := 1 to n
    for j := 1 to 2n
        x := x + 1

i := 1; j := 64
while i < j
    m := floor((i + j) / 2)
    if x > a_m then i := m + 1
    else j := m

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

for i := 1 to n
    for j := 1 to i
        for k := 1 to j
            s := s + 1