2.2_complexity_notation.md

Asymptotic notation

Throughout this module, we focus on the leading-order complexity of functions. Consider the polynomial

$$ p(n) = 3n^3 + 5n^2 + 1. $$

As $n$ becomes large, the $n^3$ term dominates the growth, making the coefficients of lower-order terms and the constant factor of the leading term negligible. To express this dominant behaviour succinctly, we use $\mathcal{O}$-notation.

:label: def-big-o-at-infinity
Let $g(x)$ and $f(x)$ be functions defined for $x \in \mathbb{X}$, $\mathbb{X} \in \{ \mathbb{N}, \mathbb{R} \}$. If there exist an $x_0 \in \mathbb{X}$ and a constant $C > 0$ such that

$$
|g(x)| \leq C|f(x)|
$$

for all $x \geq x_0$, we write $g(x) = \mathcal{O}(f(x))$ as $x \to \infty$.

The $\mathcal{O}$-notation can also be used to describe how a function approaches a finite value $y \in \mathbb{X}$. The most common case is $y = 0$.

:label: def-big-o-at-point
Let $g(x)$ and $f(x)$ be functions defined for $x \in \mathbb{X}$, $\mathbb{X} \in \{ \mathbb{N}, \mathbb{R} \}$. If there exist a $\delta > 0$ and a constant $C > 0$ such that

$$
|g(x)| \leq C|f(x)|
$$

for all $x \in B_\delta(y) := \{ x \in \mathbb{X} : | x - y | \leq \delta \} $, we write $g(x) = \mathcal{O}(f(x))$ as $x \to y$.

In most cases, when studying approximations near a finite point $y$, $f$ is chosen so that $f(x) \to 0$ as $x \to y$.

Cost of LU decomposition

We have established that solving a triangular system requires $\mathcal{O}(n^2)$ operations. For computing the decomposition $A = LU$, the operation count yields a cost of $\frac{2}{3}n^3 + \mathcal{O}(n^2)$ operations. Thus, the dominant computational cost lies in the LU decomposition itself. Once the decomposition is computed, the forward and backward substitution steps are comparatively inexpensive.

This efficiency becomes particularly advantageous when solving multiple linear systems where the matrix $A$ remains the same but the right-hand side $b$ changes. In such cases, the $LU$ decomposition is computed only once, and subsequent solutions require only the forward and backward substitutions, which can be performed efficiently.

Python skills

Below is a simple Python demonstration that illustrates the concept of dominant terms and how differences in growth rates can be empirically observed. While $\mathcal{O}$-notation is a mathematical concept, this code can give an intuitive feel for how one term outpaces another as input sizes grow.

def f(n):
    # Suppose f(n) = 3n^3 + 5n^2 + 1
    return 3*n**3 + 5*n**2 + 1

def g(n):
    # Suppose g(n) = n^3
    return n**3

# We'll measure execution times for different input sizes
input_sizes = [10, 100, 1000, 10_000, 100_000]

print("n\tf(n)\tg(n)\tf(n)/g(n)")
for n in input_sizes:
    # Compute the values
    fn = f(n)
    gn = g(n)

    ratio = fn/gn if gn != 0 else float('inf')
    print(f"{n}\t{fn}\t{gn}\t{ratio:.2f}")

By running this script, you will see that as $n$ grows, $f(n)/g(n)$ approaches a constant (in this case $3$), indicating that the cubic term is the dominant part of $f(n)$.

The ratio stabilises because both $f(n)$ and $g(n)$ grow at the same asymptotic rate ($n^3$), and the leading coefficient of $f$ is $3$. This aligns with $f(n) = \mathcal{O}(n^3)$.

To push the demonstration further, you could compare $f(n)$ to $h(n)=n^4$, where $h(n)$ grows faster. You would see that $f(n)/h(n) \to 0$ as $n$ grows, illustrating that $f(n)$ is $\mathcal{O}(n^4)$, but $h(n)$ is not $\mathcal{O}(n^3)$.

Self-check questions

:class: tip
Determine the relationship between $f(n)$ and $g(n)$ as $n \to \infty$ for the following pairs of functions. That is, decide if $f(n) = \mathcal{O}(g(n))$, $g(n) = \mathcal{O}(f(n))$, both, or neither.

1. $f(n) = n^2$ and $g(n) = n^3$
2. $f(n) = n^2 + n$ and $g(n) = n^2$
3. $f(n) = n\log n$ and $g(n) = n^2$

**Pair $f(n) = n^2$, $g(n) = n^3$:** As $n \to \infty$, $n^3$ grows faster than $n^2$. Formally, $ \frac{n^2}{n^3} = \frac{1}{n} \to 0$. This shows $n^2$ grows no faster than $n^3$, so $f(n) = \mathcal{O}(n^3)$.  However, $\frac{n^3}{n^2} = n \to \infty,$ so $n^3$ is not bounded above by a constant multiple of $n^2$. Thus $g(n) \neq \mathcal{O}(f(n))$. Conclusion: $f(n) = \mathcal{O}(g(n))$ but not vice versa.

**Pair $f(n) = n^2 + n$, $g(n) = n^2$:** As $n \to \infty$, $n^2 + n$ and $n^2$ differ only by a lower-order term. In fact, $n^2 + n \leq n^2 + n^2 = 2n^2 \text{ for } n \geq 1,$ so $f(n) = \mathcal{O}(n^2)$.  Conversely, $n^2 \leq n^2 + n \text{ for all } n \geq 1,$ so $n^2 = \mathcal{O}(n^2 + n)$. Hence, $g(n) = \mathcal{O}(f(n))$. Conclusion: $f(n) = \mathcal{O}(g(n))$ and $g(n) = \mathcal{O}(f(n))$.

**Pair $f(n) = n \log n$, $g(n) = n^2$:** As $n \to \infty$, $n^2$ grows faster than $n \log n$. Formally, $\frac{n \log n}{n^2} = \frac{\log n}{n} \to 0.$ Thus $f(n) = \mathcal{O}(n^2)$.  However, $\frac{n^2}{n \log n} = \frac{n}{\log n} \to \infty,$ so $g(n)$ is not $\mathcal{O}(f(n))$. Conclusion: $f(n) = \mathcal{O}(g(n))$ but not vice versa.

:class: tip
Suppose $f(n) = \mathcal{O}(n)$ and $g(n) = \mathcal{O}(n)$. Prove or disprove that $f(n)g(n) = \mathcal{O}(n^2)$.

By the definition of $\mathcal{O}$-notation, if $f(n) = \mathcal{O}(n)$, then there exist constants $C_f > 0$ and $n_f$ such that $|f(n)| \leq C_f n$ for all $n \geq n_f$. Similarly, if $g(n) = \mathcal{O}(n)$, then there exist constants $C_g > 0$ and $n_g$ such that $|g(n)| \leq C_g n$ for all $n \geq n_g$.

To consider $f(n)g(n)$, choose $n_0 = \max(n_f, n_g)$, ensuring both inequalities hold for $n \geq n_0$. Then, for all $n \geq n_0$:

$$
|f(n)g(n)| \leq (C_f n)(C_g n) = (C_f C_g) n^2.
$$

This shows that $f(n)g(n)$ is bounded above by a constant multiple of $n^2$ for sufficiently large $n$, hence $f(n)g(n) = \mathcal{O}(n^2)$ and the statement is true.

:class: tip
Let $A\in\mathbb{R}^{n\times n}$ be tridiagonal, that is only the main diagonal and the first upper and lower off-diagonals can be nonzero.

Assume that an LU decomposition exists. Show that it can be computed in $\mathcal{O}(n)$ operations.

In each outer loop of the Gaussian elimination only one off-diagonal element needs to be reduced. Hence, the cost for each outer loop is constant and independent of $n$, leading to a total cost of $\mathcal{O}(n)$.