Part 00•Chapter 3 of 4•Foundational

Mathematical Notation & Symbols Reference

Complete glossary of set theory, asymptotic bounds, discrete math symbols, and recurrence notation.

~15 min read

2,962 words

16 Sections

Academic Syllabus • Verified 2026

Keys: [ Prev • ] Next

Set NotationSummations & LogarithmsGraph Formalisms

Precise mathematical notation and unambiguous pseudocode syntax prevent misinterpretations between theoretical proofs and executable software.

This chapter establishes the universal mathematical symbols, asymptotic definitions, graph formalisms, pointer conventions, and language-independent pseudocode standards used across the entire curriculum.

Learning Objectives

By the end of this chapter, you will be able to:

Interpret and apply formal set theory, first-order predicate logic, and interval notations in algorithmic definitions.
Distinguish between all five standard asymptotic bounding symbols ( $O, Ω, Θ, o, ω$ ) and the soft-O notation ( $O ~$ ) used in advanced algorithms.
Read and author standardized, language-independent algorithmic pseudocode adhering to the CLRS (Cormen et al.) academic specification.
Map abstract pointer models (HEAD, TAIL, node.next, adj[u]) to concrete memory references in C++, Java, Python, Go, and Rust.
Formulate loop invariants with explicit mathematical preconditions, maintenance conditions, and postconditions.

1. Discrete Mathematics, Logic & Set Notations

Algorithmic specifications rely on standard discrete mathematics to define data domains, problem constraints, and operational bounds:

Set Theory Notations

Symbol	Mathematical Name	Formal Definition	Concrete Algorithmic Usage
$\in$	Element Of	$x \in S$ indicates element $x$ belongs to set $S$	Key membership: $k \in keys (H)$
$\in /$	Not An Element Of	$x \in / S ⟺ \neg (x \in S)$	Disjoint element check
$\subseteq$	Subset	$A \subseteq B ⟺ \forall x (x \in A ⟹ x \in B)$	Graph vertex subsets $S \subseteq V$
$\subset$	Strict / Proper Subset	$A \subset B ⟺ A \subseteq B \land A \neq = B$	Proper partition cuts in graphs
$\emptyset$	Empty / Null Set	The unique set containing zero elements: ${}$	Base condition for collections
$\cup$	Set Union	$A \cup B = {x : x \in A \lor x \in B}$	Merging disjoint sets in DSU
$\cap$	Set Intersection	$A \cap B = {x : x \in A \land x \in B}$	Finding common neighbors in graphs
$∖$	Set Difference	$A ∖ B = {x : x \in A \land x \in / B}$	Unvisited vertices: $V ∖ S$
$\times$	Cartesian Product	$A \times B = {(a, b) : a \in A \land b \in B}$	Edge domain $E \subseteq V \times V$
$∣ S ∣$	Set Cardinality	The number of distinct elements in set $S$	Vertex count $∣ V ∣$ , edge count $∣ E ∣$

Number Domains & Numerical Sets

Domain	Name	Definition	Common Role in Algorithms
$N$	Natural Numbers	${0, 1, 2, 3, \dots}$ or ${1, 2, 3, \dots}$	Array sizes, loop step counters, tree depths
$Z$	Integers	${\dots, - 2, - 1, 0, 1, 2, \dots}$	Signed array values, negative edge weights
$Q$	Rational Numbers	${p / q : p, q \in Z, q \neq = 0}$	Exact fractional fractional knapsack ratios
$R$	Real Numbers	Continuous real number line	Geometric coordinates, floating-point weights
$R^{+}$	Positive Real Numbers	${x \in R : x > 0}$	Strict non-negative weights for Dijkstra

Predicate Logic & Proof Operators

Symbol	Meaning	Example Statement	English Translation
$\forall$	Universal Quantifier	$\forall x \in A, x \geq 0$	"For all elements $x$ in $A$ , $x$ is non-negative."
$\exists$	Existential Quantifier	$\exists v \in V s.t. de g (v) = 0$	"There exists at least one vertex $v$ with degree 0."
$\exists!$	Unique Existential Quantifier	$\exists! r \in V s.t. indeg (r) = 0$	"There exists exactly one unique root node $r$ ."
$⟹$	Material Implication	$u \in S ⟹ visited [u] = true$	"If $u$ is in $S$ , then $u$ is marked visited."
$⟺$	Logical Equivalence	$f (n) \in Θ (g) ⟺ f \in O (g) \land f \in Ω (g)$	"if and only if" (bidirectional implication)
$\land$	Logical Conjunction (AND)	$i < n \land A [i] = k$	Both conditions must simultaneously evaluate true
$\lor$	Logical Disjunction (OR)	$p == NULL \lor p \to val == 0$	True if at least one operand evaluates true
$\neg$	Logical Negation (NOT)	$\neg found$	Inverts the boolean truth value

Intervals, Rounding & Summations

Notation	Formal Name	Definition / Property
$[a, b]$	Closed Interval	${x \in R : a \leq x \leq b}$ (Both boundary endpoints included)
$(a, b)$	Open Interval	${x \in R : a < x < b}$ (Both boundary endpoints excluded)
$[a, b)$	Left-Closed, Right-Open	${x \in R : a \leq x < b}$ (Standard for array slicing `A[0:n]`)
$⌊ x ⌋$	Floor Function	$max {m \in Z : m \leq x}$ (e.g., $⌊ 3.9 ⌋ = 3$ , $⌊ - 1.2 ⌋ = - 2$ )
$⌈ x ⌉$	Ceiling Function	$min {m \in Z : m \geq x}$ (e.g., $⌈ 3.1 ⌉ = 4$ , $⌈ - 1.2 ⌉ = - 1$ )
$\sum_{i = a}^{b} f (i)$	Summation Operator	$f (a) + f (a + 1) + \dots + f (b)$ (Loops and operation counting)
$\prod_{i = a}^{b} f (i)$	Product Operator	$f (a) \cdot f (a + 1) \dots f (b)$ (Factorials and permutations)
$lo g n$	Binary Logarithm	Strictly $lo g_{2} (n)$ in computer science unless specified otherwise

2. Asymptotic & Complexity Notations

Asymptotic notation captures the rate of growth of resource consumption as $n \to \infty$ , ignoring machine constants:

Asymptotic Symbol	Bound Role	Formal Mathematical Definition	Relational Analog
$O (g (n))$	Asymptotic Upper Bound	$0 \leq f (n) \leq c \cdot g (n) \forall n \geq n_{0}$	$f (n) \leq g (n)$
$Ω (g (n))$	Asymptotic Lower Bound	$0 \leq c \cdot g (n) \leq f (n) \forall n \geq n_{0}$	$f (n) \geq g (n)$
$Θ (g (n))$	Asymptotically Tight Bound	$c_{1} g (n) \leq f (n) \leq c_{2} g (n) \forall n \geq n_{0}$	$f (n) \equiv g (n)$
$o (g (n))$	Strict Asymptotic Upper Bound	$lim_{n \to \infty} \frac{f ( n )}{g ( n )} = 0$	$f (n) < g (n)$
$ω (g (n))$	Strict Asymptotic Lower Bound	$lim_{n \to \infty} \frac{f ( n )}{g ( n )} = \infty$	$f (n) > g (n)$
$O ~ (g (n))$	Soft-O (Polylog-Suppressed)	$O (g (n) \cdot lo g^{k} g (n)) for some k \geq 0$	Suppresses $lo g^{k} n$

[!NOTE] Soft-O ( $O ~$ ) Notation: In advanced algorithm design (e.g., fast Fourier transform, computational geometry, randomized matrix multiplication), algorithms frequently feature polylogarithmic factors like $O (n lo g^{3} n)$ or $O (n lo g n lo g lo g n)$ . Soft-O notation suppresses all polylogarithmic terms:
$O ~ (g (n)) = O (g (n) \cdot lo g^{k} g (n)) for some constant k \geq 0$ For instance, an algorithm running in $O (n lo g^{2} n)$ time is concisely written as $O ~ (n)$ .

3. Graph Theory Formalisms & Topologies

Graphs represent relational topologies. Standardized notation ensures clarity across shortest paths, flows, and network traversals:

Undirected Edge: e = (u, v) u Weight: w(u, v) v

Directed Arc: (u → v) u Tail Arc (u, v) v Head

Graph Formalism	Mathematical Symbol	Exact Definition / Invariant
Graph Structure	$G = (V, E)$	$V$ is the set of vertices (nodes); $E$ is the set of edges (pairs of vertices).
Vertex Cardinality	$∣ V ∣$ or $V$	Total number of vertices in graph $G$ .
Edge Cardinality	$∣ E ∣$ or $E$	Total number of edges in graph $G$ . (For simple graphs, $0 \leq ∣ E ∣ \leq (2 ∣ V ∣)$ ).
Edge Weight Function	$w : E \to R$	Maps every edge $(u, v) \in E$ to a real-valued scalar cost $w (u, v)$ .
Vertex Degree	$de g (u)$	Count of incident edges connected to vertex $u$ in an undirected graph.
In-Degree / Out-Degree	$deg^{-} (u), deg^{+} (u)$	Number of incoming and outgoing directed edges in a digraph.
Adjacency Set	$Adj [u]$ or $N (u)$	The neighborhood set of vertices adjacent to vertex $u$ : ${v \in V : (u, v) \in E}$ .
Path	$p = ⟨ v_{0}, v_{1}, \dots, v_{k} ⟩$	A sequence of vertices such that $(v_{i - 1}, v_{i}) \in E$ for all $1 \leq i \leq k$ .
Simple Path	—	A path where all vertices $v_{0}, v_{1}, \dots, v_{k}$ are mutually distinct.
Cycle	—	A path where $k \geq 3$ (undirected) or $k \geq 1$ (directed) and $v_{0} = v_{k}$ .
Directed Acyclic Graph	DAG	A directed graph possessing zero directed cycles; topological order is guaranteed.

4. Pointer Conventions & Multi-Language Concrete Mapping

Abstract data structures rely on relational pointers to link memory cells. In this curriculum, pseudocode uses standardized symbolic accessors mapped to idiomatic syntax across modern systems languages:

Abstract Pseudocode	Memory Semantic	C++20	Java / C#	Python 3	Rust
`HEAD`	Pointer to first node	`Node* head;`	`Node head;`	`self.head`	`Option<Box<Node>>`
`TAIL`	Pointer to last node	`Node* tail;`	`Node tail;`	`self.tail`	`*mut Node`
`node.val`	Value payload	`node->val`	`node.val`	`node.val`	`node.val`
`node.next`	Forward pointer	`node->next`	`node.next`	`node.next`	`node.next.as_deref()`
`node.prev`	Backward pointer	`node->prev`	`node.prev`	`node.prev`	`node.prev`
`NULL` / `NIL`	Null address	`nullptr`	`null`	`None`	`None`
`allocate(Node)`	Heap allocation	`new Node()`	`new Node()`	`Node()`	`Box::new(Node::new())`
`free(node)`	Deallocate memory	`delete node;`	Managed by GC	Managed by GC	Dropped at scope end

5. The CLRS Algorithmic Pseudocode Standard

To maintain rigorous mathematical precision without tying algorithms to language-specific runtime quirks, all pseudocode in this curriculum follows the CLRS (Introduction to Algorithms) convention:

Syntactic & Formatting Rules

Explicit Line Numbering: Every executable statement is assigned a unique line number for direct analysis in proofs and operation counting.
Indentation Indicates Block Scope: Blocks of code (loop bodies, conditional branches) are delimited strictly by indentation rather than braces ({}) or begin/end keywords.
Compound Data Variables: Attributes are accessed using object notation: A.length, node.next, T.root.
Assignment Operator: Assignment is denoted by a left-pointing arrow $\leftarrow$ (or := in text), strictly distinguishing assignment from equality testing ( $=$ ).
Array Indexing: Unless explicitly noted otherwise for competitive programming contexts, theoretical pseudocode uses 1-based indexing ( $A [1 \dots n]$ ), with subarrays specified as $A [p \dots r]$ .
Pass-by-Reference for Objects: Arrays and composite data structures are passed by reference; primitive scalars are passed by value.

Canonical Pseudocode Example: Insertion Sort with Invariant

      
      Algorithm Pseudocode — InsertionSort(A, n)
      Formal Spec

1ALGORITHM InsertionSort(A, n)
2INPUT: An array A containing n elements: A[1...n]
3OUTPUT: The array A sorted in monotonically non-decreasing order: A[1] <= A[2] <= ... <= A[n]
4 
51.  for j = 2 to n do
62.      key ← A[j]
73.      // INVARIANT: The subarray A[1...j-1] consists of elements originally
84.      // in A[1...j-1], but in strictly sorted ascending order.
95.      i ← j - 1
106.      while i > 0 and A[i] > key do
117.          A[i + 1] ← A[i]
128.          i ← i - 1
139.      A[i + 1] ← key
1410. return A

6. Loop Invariants: Structure & Formal Proof Template

A Loop Invariant is a formal predicate about the state of an algorithm that remains true before and after each iteration of a loop. It serves as the primary tool for proving the partial correctness of iterative algorithms.

Every formal loop invariant proof must establish three mandatory phases:

System Architecture Mermaid

flowchart LR
    P1["1. INITIALIZATION<br/><small>True prior to 1st iteration<br/>(Base Step: induction foundation)</small>"] --> 
    P2["2. MAINTENANCE<br/><small>True before iteration ⇒ True after<br/>(Inductive Step: invariant preserved)</small>"] --> 
    P3["3. TERMINATION<br/><small>Holds at loop exit condition<br/>(Yields partial correctness proof)</small>"]

Invariant Proof Walkthrough: Insertion Sort

Invariant: At the start of each iteration of the outer for loop (line 1), the subarray $A [1 \dots j - 1]$ consists of the elements originally in $A [1 \dots j - 1]$ , but in sorted ascending order.

Initialization (Base Case):
- Prior to the first iteration, $j = 2$ .
- The subarray consists of the single element $A [1 \dots 1]$ .
- Any single-element array is trivially sorted. Thus, the invariant holds before loop entry.
Maintenance (Inductive Step):
- Assume the invariant holds for an index $j$ : $A [1 \dots j - 1]$ is sorted.
- Lines 5–8 shift elements $A [j - 1], A [j - 2], \dots$ to the right until the correct position for key ( $A [j]$ ) is identified.
- Line 9 inserts key into this slot.
- Subarray $A [1 \dots j]$ now contains the exact same elements as before, but with key inserted in its sorted position.
- Incrementing $j$ for the next iteration maintains the invariant for the new subarray $A [1 \dots j - 1]$ .
Termination:
- The loop terminates when $j > n$ . Since $j$ increments by $1$ per step, it terminates precisely when $j = n + 1$ .
- Substituting $j = n + 1$ into the invariant statement: The subarray $A [1 \dots (n + 1) - 1] = A [1 \dots n]$ consists of the original elements of $A [1 \dots n]$ in sorted ascending order.
- The entire array is sorted! The algorithm is formally proven correct. $■$

7. Key Takeaways & Notation Quick Reference

Asymptotics: Always use $Θ$ when an upper and lower bound match; reserve $O$ for upper bounds and $Ω$ for theoretical lower limits.
Interval Bounds: Differentiate closed intervals $[0, n]$ ( $n + 1$ items) from half-open intervals $[0, n)$ ( $n$ items).
CLRS Pseudocode: Treat pseudocode as executable mathematical specifications with explicit block scoping and invariant statements.
Loop Invariants: Validate correctness using the tripartite template: Initialization, Maintenance, and Termination.

References & Academic Attribution

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Section 2.1: "Insertion sort" & Chapter 3: "Growth of Functions". MIT Press.
Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (3rd ed.), Section 1.1: "Algorithms". Addison-Wesley.
Rosen, K. H. (2019). Discrete Mathematics and Its Applications (8th ed.). McGraw-Hill.