---
title: "Notation and Symbols"
summary: Every symbol this book uses, the standard complexity table, and the terminology that differs between communities.
difficulty: core
tags: [reference, notation]
prereq: [foundations/types]
see: [appendix/template, complexity/classes]
---

:::props title="Graphs"
| symbol | meaning | first used |
|---|---|---|
| $G=(V,E)$, $n=|V|$, $m=|E|$ | the graph and its sizes | @foundations/types |
| $N(v)$, $N[v]$ | open / closed neighbourhood of $v$ | @foundations/types |
| $\deg(v)$, $\delta(G)$, $\Delta(G)$ | degree, minimum and maximum degree | @foundations/types |
| $\bar G$ | complement | @foundations/subgraph |
| $G[S]$, $G - S$ | induced subgraph, deletion of a vertex set | @foundations/subgraph |
| $G/e$, $G - e$ | edge contraction, edge deletion | @proofs/contracting |
| $H \preceq_m G$ | $H$ is a **minor** of $G$ (deletions + contractions) | @special/planar |
| $\omega(G)$, $\alpha(G)$, $\chi(G)$, $\chi'(G)$ | clique, independent set, chromatic, chromatic index | @special/coloring |
| $\kappa(G)$, $\lambda(G)$ | vertex- and edge-connectivity | @foundations/connectivity |
| $G^*$ | planar dual | @special/planar |
| $\operatorname{ecc}(v)$, $\operatorname{rad}(G)$, $\operatorname{diam}(G)$ | eccentricity, radius, diameter | @trees/diameter |
| $\operatorname{cen}(G)$ | centre (one vertex or an edge) | @trees/diameter |
| $\operatorname{dist}(u,v)$ | shortest-path distance (number of edges, or $\sum$ weights) | @trees/distance |
| $A^k_{uv}$ | number of walks of length $k$ from $u$ to $v$ | @matrices/walks-powers |
| $L = D - A$, $\tau(G)$ | Laplacian, number of spanning trees | @matrices/matrix-tree |
| $\operatorname{tin}[v]$, $\operatorname{tout}[v]$ | DFS entry/exit times | @trees/euler-tour |
| $\operatorname{depth}[v]$, $\operatorname{par}[v]$, $\operatorname{sub}[v]$ | rooted-tree depth, parent, subtree size | @trees/dfs |
| $\operatorname{lca}(u,v)$ | lowest common ancestor | @lca/problem |
| $M$, $\nu(G)$, $\mu(G)$ | a matching, its maximum size (two conventions) | @matching/intro |
| $\tau_v(G)$ | minimum vertex cover size (some books write $\beta$) | @matching/konig |
| $R(s,t)$, $R_k(3)$ | Ramsey numbers | @special/ramsey |
| $\Delta$, $\nabla$ | max degree; also the Laplacian operator in @special/random-walk | — |
:::

:::props title="Complexity and asymptotics"
| notation | meaning |
|---|---|
| $O(f)$, $\Omega(f)$, $\Theta(f)$ | upper, lower, both — and in this book $O(\cdot)$ is worst-case unless "expected" is written |
| $\tilde O(f)$ | $O(f \log^{c} f)$ for some constant $c$ |
| $[n]$ | the set $\{1,\dots,n\}$ (or $\{0,\dots,n-1\}$ in code) |
| $\binom nk$ | binomial coefficient; $\log\binom nk \le k\log(en/k)$, used in @special/ramsey |
| $x \bmod p$, $x^{-1}$ | residue in $[0,p)$; multiplicative inverse mod prime $p$ |
| $\alpha \le \beta + \varepsilon n$ | the "$+o(n)$"-style sloppiness in approximation statements |
| P, NP, NP-hard, NP-complete | @complexity/classes |
| FPT, XP | fixed-parameter tractable: $f(k)\,n^{O(1)}$ versus $n^{f(k)}$ — @complexity/escape |
| 3-SAT, CLIQUE, 3-DIM MATCHING | the standard sources of reductions (@complexity/npc-graphs) |
:::

:::props title="The complexity table you should be able to recite"
| bound at $n = 10^5$ | verdict |
|---|---|
| $O(n)$, $O(n\log n)$ | fine — up to $10^7$–$10^8$ operations |
| $O(n\sqrt n) \approx 3\cdot10^7$ | fine |
| $O(n\log^2 n)$, $O(n\log n)$ with big constants | fine, watch the memory |
| $O(n^2) = 10^{10}$ | too slow; $O(n^2)$ is only OK up to $n \approx 5000$ |
| $O(n^2/64)$ bitset | $1.5\cdot10^8$ word-ops — passes; the kind of trick @special/independent is about |
| $O(2^n n)$ | $n \le 22$ (@complexity/escape's Held–Karp bound) |
| $O(3^{n/3})$, $O(1.2^n)$ | $n \le 40$–$60$ — measure and conquer territory |
| $O(n!)$ | $n \le 10$ |
:::

:::note title="Where this book's terminology differs from other sources"
- **"walk" vs "path" vs "trail"**: a walk repeats freely, a trail repeats no edge, a path repeats no vertex. Upstream and several Russian texts use "path" for walks; @foundations/walks fixes the convention used here,
- **connected**: this book says "connected component" for maximal connected subgraphs and never calls a disconnected graph "connected with $k$ parts",
- **DFS order**: `tin`/`tout` here mean entry/exit *timer* values (not "the $i$-th visited vertex"); interval containment is the whole point (@trees/euler-tour),
- **tree DP** states are written $(v, 0/1)$ for "not taken/taken" — the same skeleton as @special/independent,
- **matching duality**: $\nu$ for matching size and $\tau$ for cover size, following Vizing/Kőnig usage; some books use $\alpha'$ and $\beta$,
- **0-indexed vs 1-indexed**: the code uses 0-based arrays, the math uses $[n]$. When a proof says "the parent of the root is itself", that is the code convention (@lca/problem),
- **$\log$** is base 2 inside complexity claims and base $e$ inside probabilistic ones (@special/random-walk), and it never changes an $O(\cdot)$.
:::

:::props title="Function and value names used in the code, once"
`g` adjacency list · `w` weight (function or matrix) · `dist` best known distance · `par`, `dep`, `sub` parent/depth/subtree size · `tin`, `tout` DFS times · `up[v][j]` $2^j$-ancestor · `dp[...]` table · `nxt` functional-graph successor · `mt` match partner · `lvl`, `ptr` Dinic/HK layer and cursor · `comp` component id · `INF`, `LINF` sentinels · `ret`, `res` accumulator in a function.
:::