Asymptotic notation

Lesson 1 argued that growth rate matters more than constant factors. This lesson makes that idea precise. Asymptotic notation lets us say that one function grows no faster than another, no slower, or at the same rate, while ignoring constant factors and small inputs. The notation is compact, but every statement in it is a claim with a definition behind it, and you can prove or disprove such claims with the techniques from CMPUT-272. By the end of the lesson you will be able to classify running times, prove bounds with explicit constants, and avoid the common ways the notation is misused.

Big-O: an upper bound

Let \(f\) and \(g\) be functions from the natural numbers to the non-negative real numbers. We say \(f(n)\) is \(O(g(n))\), read big-O of \(g\), if there are positive constants \(c\) and \(n_0\) such that \(f(n) \le c \cdot g(n)\) for every \(n \ge n_0\). In words: beyond some point, \(f\) never exceeds a constant multiple of \(g\). The constant \(c\) absorbs differences in machine speed and implementation detail; \(n_0\) lets us ignore small inputs where lower-order terms might dominate.

The definition is a nested-quantifier statement of exactly the kind you translated in CMPUT-272 lesson 4. To prove \(f \in O(g)\) you must exhibit specific values of \(c\) and \(n_0\) and then show the inequality for all larger \(n\). To disprove it you must show that for every choice of \(c\) and \(n_0\) there is some \(n \ge n_0\) where \(f(n) > c \cdot g(n)\). Writers often use the equals sign, as in \(3n^2 + 5n = O(n^2)\), but it means membership in a set of functions, not equality: it is never correct to flip it around and write \(O(n^2) = 3n^2 + 5n\).

The trick in that proof, replacing each lower-order term by a larger multiple of the highest-order term, works for any polynomial. It shows that a polynomial of degree \(d\) with a positive leading coefficient is \(O(n^d)\). It also shows that constants are not unique: if \(c = 10\) works, so does \(c = 11\), and a larger \(n_0\) often allows a smaller \(c\).

def check(f, g, c, n0, upto=10**5):
    """Check f(n) <= c*g(n) for n0 <= n <= upto; return first failure or None."""
    for n in range(n0, upto + 1):
        if f(n) > c * g(n):
            return n
    return None

f = lambda n: 3 * n * n + 5 * n + 2
g = lambda n: n * n
print('c=10, n0=1 :', check(f, g, 10, 1))
print('c=4,  n0=6 :', check(f, g, 4, 6))
print('c=4,  n0=1 :', check(f, g, 4, 1))      # fails for small n
print('c=3,  n0=1 :', check(f, g, 3, 1))      # c too small: fails at every n

c=10, n0=1 : None
c=4,  n0=6 : None
c=4,  n0=1 : 1
c=3,  n0=1 : 1

The check is useful for finding constants before you prove them, in the explore-then-prove style of CMPUT-272 lesson 1. Look at what the last line shows: with \(c = 3\), the bound fails immediately, because \(3n^2 + 5n + 2 > 3n^2\) for every \(n\). No choice of \(n_0\) rescues \(c = 3\); you must increase \(c\).

Big-Omega and Big-Theta

Big-O is an upper bound. The matching lower bound is big-Omega: \(f(n)\) is \(\Omega(g(n))\) if there are positive constants \(c\) and \(n_0\) with \(f(n) \ge c \cdot g(n)\) for every \(n \ge n_0\). When both hold, \(f\) and \(g\) grow at the same rate and we write \(f(n) \in \Theta(g(n))\), read big-Theta. Equivalently, there are constants \(c_1, c_2 > 0\) and \(n_0\) with \(c_1 g(n) \le f(n) \le c_2 g(n)\) for all \(n \ge n_0\).

Big-O, Omega and Theta can describe any function, not only running times. Statements such as the worst-case running time of insertion sort is \(\Theta(n^2)\) and its best-case running time is \(\Theta(n)\) are both precise and informative. Saying merely that insertion sort is \(O(n^2)\) is true but weaker, because \(O\) only gives an upper bound: insertion sort is also \(O(n^3)\) and \(O(2^n)\), which are true and useless. When you know a tight bound, state it with Theta.

Little-o, little-omega and the limit test

Sometimes we want to say that one function grows strictly slower than another. We write \(f \in o(g)\), little-o, if for every constant \(c > 0\) there is an \(n_0\) with \(f(n) < c\, g(n)\) for all \(n \ge n_0\). The quantifier on \(c\) has changed from there exists to for every, which is what makes the relation strict. Similarly \(f \in \omega(g)\) means \(g \in o(f)\). For example \(n \in o(n^2)\), but \(n^2 \notin o(n^2)\).

Limits often make classification quick. If the limit of \(f(n)/g(n)\) as \(n\) goes to infinity exists and equals \(L\), then: \(L = 0\) means \(f \in o(g)\) and hence \(f \in O(g)\); \(0 < L < \infty\) means \(f \in \Theta(g)\); and \(L = \infty\) means \(f \in \omega(g)\) and hence \(f \in \Omega(g)\). The test does not apply when the limit fails to exist, for example for functions that oscillate, so the definitions remain the final authority.

import math
pairs = [('n log2 n', 'n^2', lambda n: n * math.log2(n), lambda n: n * n),
         ('n^2', '2^n', lambda n: n * n, lambda n: 2 ** n),
         ('(log2 n)^3', 'n', lambda n: math.log2(n) ** 3, lambda n: n),
         ('5n^2 + n', 'n^2', lambda n: 5 * n * n + n, lambda n: n * n)]
for fn, gn, f, g in pairs:
    ratios = [f(n) / g(n) for n in (2**4, 2**8, 2**12, 2**16)]
    print(f'{fn:>11} / {gn:<4}', ' '.join(f'{r:.4g}' for r in ratios))

   n log2 n / n^2  0.25 0.03125 0.00293 0.0002441
        n^2 / 2^n  0.003906 5.66e-73 0 0
 (log2 n)^3 / n    4 2 0.4219 0.0625
   5n^2 + n / n^2  5.062 5.004 5 5

The ratios suggest the limits: \(n \log n / n^2\) heads to 0, \(n^2 / 2^n\) collapses to 0 very fast, and \(5n^2 + n\) over \(n^2\) approaches 5, so it is Theta of \(n^2\). The third row is instructive: \((\log_2 n)^3 / n\) starts at 4 when \(n = 16\), meaning the cubed logarithm is still larger than \(n\), and only then falls toward 0. Any power of a logarithm grows more slowly than any positive power of \(n\), but the crossover can be far out: \((\log_2 n)^{10}\) stays above \(n\) until about \(n = 2^{59}\), which is more than \(5 \times 10^{17}\). Numerical ratios are evidence; L'Hôpital's rule or a direct argument provides the proof.

The hierarchy of common functions

The following chain, in which each function is little-o of the next, covers almost every running time in this course: \(1\), \(\log n\), \(\sqrt{n}\), \(n\), \(n \log n\), \(n^2\), \(n^3\), \(2^n\), \(n!\), \(n^n\). Three facts underlie it. Every logarithm grows more slowly than every positive power: \((\log n)^k \in o(n^\epsilon)\) for all \(k\) and every \(\epsilon > 0\). Every polynomial grows more slowly than every exponential with base greater than 1: \(n^k \in o(b^n)\) for \(b > 1\). And \(n!\) lies between \(2^n\) and \(n^n\), with Stirling's approximation showing \(\log_2(n!) \in \Theta(n \log n)\), a fact lesson 5 uses for the sorting lower bound.

The base of a logarithm does not matter inside asymptotic notation, because \(\log_a n = \log_b n / \log_b a\) and \(1/\log_b a\) is a constant. That is why we write \(O(\log n)\) without a base. The base of an exponential does matter: \(3^n\) is not \(O(2^n)\), since \(3^n / 2^n = 1.5^n\) grows without bound.

Rules for combining bounds

Analysing an algorithm usually means combining bounds for its parts. A few rules, each provable from the definitions, cover most cases. Constant factors can be dropped: if \(f \in O(g)\) then \(k f \in O(g)\) for any constant \(k > 0\). Sums are dominated by the larger term: \(f_1 + f_2 \in O(\max(g_1, g_2))\) when \(f_1 \in O(g_1)\) and \(f_2 \in O(g_2)\). Products multiply: \(f_1 f_2 \in O(g_1 g_2)\). And the relation is transitive: \(f \in O(g)\) and \(g \in O(h)\) give \(f \in O(h)\). The same rules hold for Omega and Theta.

What asymptotic notation does not say

A bound like \(\Theta(n \log n)\) hides two things you sometimes care about. It hides constant factors, which can make an asymptotically worse algorithm faster for every input you will actually see, as lesson 1's crossover example showed. And it says nothing about small inputs, below \(n_0\). Asymptotic notation also describes a function; you must still say which function: worst-case time, average-case time, best case, or memory. The sentence quicksort is \(O(n \log n)\) is false for the worst case and true for the average case, so a careful writer always names the case.