Source: "Building Blocks for Theoretical Computer Science" by Prof. Margaret Fleck, Chapters 3, 6–9, 11–14
Tags: recursion, recursive definition, Big O, asymptotic analysis, binary search, merge sort, relations, functions, reflexive, symmetric, transitive, equivalence, one-to-one, onto, graph theory, tree, mathematical induction, UIUC CS225, CS173
Difficulty: Intermediate | Prerequisites: CS 173 or equivalent discrete mathematics course. Comfort with basic proof techniques.
CS 225 assumes fluency in several discrete maths concepts from CS 173. These are not just background knowledge: they appear directly in exam questions. Recursive definitions are tested through code that uses recursion. Big O notation is how you express and compare running times for every data structure operation. Relations and functions supply the formal language for understanding ordered, sorted, and equivalent structures. Graph and tree terminology names the structures you will implement. Induction is the proof technique used to verify claims about recursive algorithms and resize strategies. If any of these feel unfamiliar, prioritise reviewing them before the data structures content.
You need recursive definitions to read and write recursive code, Big O to analyse running times, relations and functions to reason about data structure properties, graph and tree vocabulary to describe structures precisely, and induction to prove correctness and complexity claims. These topics are interwoven through CS 225, not separate modules.
Recursive definition
A definition where an object is defined in terms of simpler instances of itself, together with one or more base cases that stop the recursion.
Think of it as Russian nesting dolls: each doll contains a smaller version of itself until you reach the smallest one (the base case).
Base case
The condition in a recursive definition where the answer is given directly, without further recursion.
In simple terms, the point where you stop calling yourself and return a concrete value.
Big O notation, O(f(n))
A mathematical notation describing an upper bound on growth rate. g(n) is O(f(n)) if there exist constants c > 0 and n₀ such that g(n) ≤ c · f(n) for all n ≥ n₀.
Think of it as saying, "This function grows no faster than f(n), once n gets large enough."
Big Omega, Ω(f(n))
A lower bound on growth rate. g(n) is Ω(f(n)) if there exist constants c > 0 and n₀ such that g(n) ≥ c · f(n) for all n ≥ n₀.
In simple terms, "This function grows at least as fast as f(n)."
Big Theta, Θ(f(n))
A tight bound: g(n) is Θ(f(n)) if it is both O(f(n)) and Ω(f(n)).
Think of it as pinning down the exact growth rate, up to constant factors.
Reflexive relation
A relation R on a set A where every element is related to itself: for all a in A, (a, a) ∈ R.
In simple terms, every element "points to itself."
Symmetric relation
A relation where if (a, b) ∈ R then (b, a) ∈ R.
Think of it as a two-way street: if a is related to b, then b is related to a.
Transitive relation
A relation where if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.
In simple terms, the relation chains: if a connects to b and b connects to c, then a connects to c directly.
Equivalence relation
A relation that is reflexive, symmetric, and transitive. It partitions a set into disjoint equivalence classes.
Think of it as grouping elements into clusters where everything within a cluster is "the same" in some defined sense.
One-to-one (injective) function
A function where distinct inputs always produce distinct outputs: if f(a) = f(b), then a = b.
In simple terms, no two different inputs share the same output.
Onto (surjective) function
A function where every element in the codomain is mapped to by at least one element in the domain.
Think of it as "every target gets hit."
Graph
A pair G = (V, E) where V is a set of vertices and E is a set of edges connecting pairs of vertices.
In simple terms, a collection of dots (vertices) and lines (edges) between them.
Tree
A connected, acyclic graph. In CS, usually rooted: one vertex is designated the root, and every other vertex has exactly one parent.
Think of it as a family tree: one ancestor at the top, branches going down, and no loops.
Mathematical induction
A proof technique with two steps. Base case: show the statement holds for the smallest value. Inductive step: assume the statement holds for some arbitrary k (the inductive hypothesis), and use that assumption to prove it holds for k + 1.
In simple terms, knock over the first domino (base case), then show that any fallen domino knocks over the next (inductive step).
A recursive function must have at least one base case and at least one recursive call that moves toward the base case.
When reading recursive code, trace it by hand: write out the call stack and the return values.
Common exam pattern: given a recursive function, determine its output for a specific input.
A recursive definition that never reaches its base case results in infinite recursion (stack overflow in practice).
Ordered from slowest to fastest growth:
O(1) , constant
O(log n) , logarithmic (binary search)
O(n) , linear (single traversal)
O(n log n) , linearithmic (merge sort)
O(n²) , quadratic (nested loops)
O(2ⁿ) , exponential
Key algorithms and their complexities:
Binary search on a sorted array: O(log n). Each comparison eliminates half the remaining elements.
Merge sort: O(n log n). The array is split in half recursively (log n levels), and each level does O(n) work to merge.
Linear search: O(n). Check each element one by one.
Simple nested loop (e.g. bubble sort): O(n²).
When proving Big O, find constants c and n₀ explicitly. For example, to show that 3n + 5 is O(n): choose c = 4, n₀ = 5. Then 3n + 5 ≤ 4n for all n ≥ 5.
Reflexive, symmetric, transitive are the three properties tested independently. Exam questions may give you a relation on a small set and ask which properties it has.
An equivalence relation requires all three. The resulting equivalence classes partition the set with no overlap.
Ordered relations (partial and total orders) are reflexive, antisymmetric, and transitive.
One-to-one and onto apply to functions. A function that is both is a bijection (one-to-one correspondence).
To check if a function is one-to-one: show no two inputs map to the same output. To check if it is onto: show every output is reached.
Vertex (node): a fundamental unit of a graph.
Edge: a connection between two vertices.
Degree: the number of edges incident to a vertex.
Path: a sequence of vertices connected by edges.
Cycle: a path that starts and ends at the same vertex with no repeated edges.
Connected graph: there is a path between every pair of vertices.
Directed graph (digraph): edges have a direction (arrows).
Undirected graph: edges have no direction.
Root: the top node of a rooted tree.
Parent / child: if edge (u, v) exists and u is closer to the root, u is the parent and v is the child.
Leaf: a node with no children.
Depth: the number of edges from the root to a node.
Height: the number of edges on the longest path from a node to a leaf. The height of the tree is the height of the root.
Subtree: any node together with all its descendants forms a subtree.
A tree with n nodes has exactly n - 1 edges.
Step 1, base case: verify the statement for the smallest value (often n = 0 or n = 1).
Step 2, inductive hypothesis: assume the statement holds for an arbitrary n = k.
Step 3, inductive step: prove the statement holds for n = k + 1, using the assumption.
Strong induction: the inductive hypothesis assumes the statement holds for all values up to k, not just for k.
Induction is used in CS 225 to prove properties of recursive algorithms and to prove the amortised cost of resize strategies.
Geometric series (used in resize proofs):
1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1
Arithmetic series (used in grow-by-one proofs):
1 + 2 + 3 + ... + n = n(n + 1) / 2
Tree property:
A tree with n nodes has exactly n - 1 edges.
Big O formal definition:
f(n) = O(g(n)) iff ∃ c > 0, n₀ > 0 such that f(n) ≤ c · g(n) for all n ≥ n₀
Big O analysis is how engineers decide which algorithm to use in production systems: an O(n log n) sort scales to millions of records where an O(n²) sort would take hours. Graph and tree terminology is the language of networks, file systems, and databases. Induction proofs underpin the correctness guarantees of any recursive system you build.
"O(n) and Θ(n) mean the same thing." O(n) is only an upper bound. An algorithm that runs in O(1) is also technically O(n). Θ(n) is a tight bound, meaning the algorithm grows both at most and at least linearly.
"If a function is one-to-one, it is also onto." Not necessarily. A function from a larger domain to a smaller codomain cannot be one-to-one at all. A function from a smaller domain to a larger codomain can be one-to-one but not onto.
"A tree can have cycles." By definition, a tree is acyclic. A connected graph with a cycle is not a tree.
"The inductive step proves the statement is true. The base case is just a formality." Both are essential. Without the base case, the chain of reasoning has no anchor. Proofs that skip the base case are invalid.
⚠️ Recursive function tracing is nearly guaranteed on the exam. Be prepared to write out the full call stack for a small input.
⚠️ Know the Big O of binary search (O(log n)), merge sort (O(n log n)), and linear search (O(n)) cold. Questions may ask you to rank algorithms or identify the complexity of a code snippet.
⚠️ Relation properties (reflexive, symmetric, transitive) are commonly tested with a small set and a list of ordered pairs.
⚠️ Tree terminology (root, leaf, depth, height) appears in both conceptual and code-reading questions.
⚠️ Induction proofs about resize strategies or recursive correctness may appear as written-response or multiple-choice questions.
True or false: O(n²) is also O(n³).
Fill in the blank: A relation that is reflexive, symmetric, and transitive is called an ________ relation.
True or false: A tree with 10 nodes has 10 edges.
Fill in the blank: The time complexity of binary search is O(________).
True or false: In a proof by induction, the base case verifies the statement for one specific value, and the inductive step shows it holds for k + 1 assuming it holds for k.
(Answers: 1. True, O(n²) ⊂ O(n³). 2. equivalence. 3. False, it has 9 edges. 4. log n. 5. True.)
Q: Given the recursive function below, what does f(4) return?
int f(int n) {
if (n == 0) return 1;
return n * f(n - 1);
}
A: This computes factorial. f(4) = 4 f(3) = 4 3 f(2) = 4 3 2 f(1) = 4 3 2 1 f(0) = 4 3 2 1 1 = 24.
Q: Is the relation R = {(1,1), (2,2), (1,2), (2,1)} on the set {1, 2} an equivalence relation?
A: Check: reflexive (both (1,1) and (2,2) present), symmetric ((1,2) and (2,1) both present), transitive ((1,2) and (2,1) imply (1,1) which is present; all other chains check out). Yes, it is an equivalence relation. The single equivalence class is {1, 2}.
Q: Prove by induction that the sum 1 + 2 + ... + n = n(n + 1) / 2.
A: Base case: n = 1. Left side: 1. Right side: 1(2)/2 = 1. Holds. Inductive step: assume 1 + 2 + ... + k = k(k + 1)/2. Then 1 + 2 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2. This is the formula with n = k + 1. QED.
Q: A function f maps {1, 2, 3} to {a, b, c, d} with f(1) = a, f(2) = b, f(3) = c. Is f one-to-one? Is f onto?
A: One-to-one: yes, distinct inputs give distinct outputs. Onto: no, the element d in the codomain is not mapped to by any input.
Q: What is the height of a single-node tree?
A: 0. The height is the number of edges on the longest root-to-leaf path. A single node has no edges below it.
Recursive definitions connect to the implementation of recursive data structures (linked lists, trees) in CS 225. Big O notation is used every time you analyse an operation on a data structure. Induction is the proof technique behind the amortised analysis of array list resizing (covered in the Array Lists and Linked Lists study notes). Graph and tree terminology become central in the second half of the course when you implement traversals, shortest paths, and spanning trees.
recursion, recursive definition, base case, Big O, Big Omega, Big Theta, asymptotic analysis, binary search, merge sort, linear search, relations, reflexive, symmetric, transitive, antisymmetric, equivalence relation, partial order, total order, one-to-one, injective, onto, surjective, bijection, graph, vertex, edge, degree, path, cycle, connected, directed graph, tree, root, leaf, depth, height, subtree, mathematical induction, strong induction, UIUC CS225, CS173, data structures exam 1