algorithmic complexity

How does an algorithm scale?
Algorithmic complexity analyses the growth-rate of an algorithm as input size approaches infinity.

Before we can analyze an algorithm, we need to decide what operations cost time.
Primitive operations, like comparisons, assignments, arithmetic operations, array access, …, but also abstract opterations like function calls, db queries, etc.

Asymptotic notation

We compare two functions $f,g:\mathbb{N}\to {\mathbb{R}}_{{\ge }_0}$.
$f(n)$ … time complexity / cost function of an algorithm with input size $n$.
$g(n)$ … a reference function for comparison

Asymptotic notation describes how $f$ relates to $g$ asymptotically (as $n\to \infty$).

Big-O — Upper bound / Worst Case

$$f\in O(g)⟺\exists c,n_0:\forall n\ge n_0,f(n)\le c\cdot g(n)$$

$f$ grows at most as fast as $g$ up to a constant factor $c$ beyond some threshold $n_0$.
It is bounded above by $g$ for large enough $n$.

E.g.: Binary search is $O(\log n)$ – even in the worst case, you don’t need more than $\log n$ comparisons.

Big-Omega — Lower bound / Best Case

$$f\in \Omega (g)⟺\exists c,n_0:\forall n\ge n_0,f(n)\ge c\cdot g(n)$$

$f$ grows at least as fast as $g$ up to a constant factor $c$ beyond some threshold $n_0$.
It is bounded below by $g$ for large enough $n$.

E.g.: Any comparison-based sorting algorithm is $\Omega (n\log n)$. You need at least $n\log n$ operations. ¹

Big-Theta — Tight bound

$$f\in \Theta (g)⟺f\in O(g)\wedge f\in \Omega (g)$$

$f$ grows at the same rate as $g$ up to constant factors $c_1,c_2$ beyond some threshold $n_0$.
It is bounded both above and below by $g$ for large enough $n$.

E.g.: Merge sort is $\Theta (n\log n)$ – in both the best and worst case, you need on the order of $n\log n$ comparisons.

Small-o — Strict upper bound

$$f\in o(g)⟺\forall c>0,\exists n_0:\forall n>n_0,f(n)<c\cdot g(n)$$

$f$ grows strictly slower than $g$, i.e. for any constant factor $c$, beyond some threshold $n_0$, $f(n)$ is less than $c\cdot g(n)$.
$\frac{f(n)}{g(n)}\to 0$ as $n\to \infty$, i.e. $f$ becomes insignificant compared to $g$ as $n$ approaches infinity.

E.g.: $\log n$ is $o(n)$ – logarithmic growth is strictly slower than linear growth.

Little omega — Strict lower bound

$$f\in \omega (g)⟺\forall c>0,\exists n_0:\forall n>n_0,f(n)>c\cdot g(n)$$

$f$ grows strictly faster than $g$, i.e. for any constant factor $c$, beyond some threshold $n_0$, $f(n)$ is greater than $c\cdot g(n)$.
$\frac{f(n)}{g(n)}\to \infty$ as $n\to \infty$, i.e. $f$ dominates $g$ as $n$ approaches infinity.

E.g.: $n$ is $\omega (\log n)$ – linear growth is strictly faster than logarithmic growth.

---

https://claude.ai/chat/6d1f89b2-5592-410a-a01f-76b0f6006bb8

https://chatgpt.com/share/68bf489c-cd80-800f-99d9-e381ab3168bb

Footnotes

1. You need ${\log }_2(n!)\approx n\log n$ (trust) bits of information to specify which of the $n!$ permutations you have. Each comparison gives you at most 1 bit. radix sort, for example, can beat this by exploiting structure in the data itself. ↩