Difficulty: Intermediate | Prerequisites: Big-O notation (see companion notes), summation notation, basic proof techniques.
Once you know asymptotic notation, the next step is applying it to real code: counting how many times a loop body executes and expressing that count in Big-O. This is the bridge between the abstract maths of growth rates and the practical question "how slow will this get?" Alongside that, mathematical induction gives you the proof technique for establishing that a formula or property holds for every positive integer, which turns up constantly in algorithm correctness arguments and summation identities.
To find the Big-O of nested loops, count the inner loop's iterations as a function of the outer variable, then sum over all outer iterations. Bubble sort's nested comparison loops give O(n^2). Mathematical induction proves a statement for all positive integers by establishing a base case and then showing that if the statement holds for k, it holds for k + 1.
Nested loop analysis
The process of determining the total number of operations by analysing the inner loop's iteration count as a function of the outer loop variable, then summing across all outer iterations.
Halving loop (logarithmic inner loop)
A loop where the control variable is divided (typically by 2) each iteration, e.g. j = j/2. Such a loop runs floor(log i) times when it starts at i. In simple terms, each step cuts the remaining work in half, which is why it produces a logarithmic count.
Bubble sort
A comparison-based sorting algorithm that repeatedly walks through the list, swapping adjacent elements that are out of order. Its total comparisons sum to (n-1) + (n-2) + ... + 1 = n(n-1)/2, giving O(n^2).
Mathematical induction
A proof technique with two parts: prove the statement for a base case (usually n = 1), then prove that if it holds for an arbitrary k, it must hold for k + 1. Together, these establish the statement for every positive integer.
Inductive hypothesis
The assumption, within the inductive step, that the proposition P(k) is true. You use this assumption to derive P(k + 1). Think of it as the "suppose it works for k" step that lets you climb from one integer to the next.
Basis step (base case)
The initial verification that the proposition holds for the smallest value in its domain (often n = 1). Without a valid base case, the entire induction argument collapses.
Worked example: outer loop with a halving inner loop
Consider this code:
for (int i = 1; i < n; i++) {
for (int j = i; j > 1; j = j/2) {
print("...");
}
}Counting the inner loop: When i = 2^k, the inner loop takes values j = 2^k, 2^(k-1), ..., 2, executing exactly k = log(i) times. For values of i between consecutive powers of 2, the count is floor(log i).
Summing over the outer loop: The outer loop runs i from 1 to n - 1. Since floor(log i) <= log n for every i < n, the total is bounded above:
Sum from i = 1 to n - 1 of floor(log i) <= (n - 1) * floor(log n) <= n log n
Tight bound: O(n log n).
The key technique: replace the varying inner count with its maximum value (log n) across all outer iterations, then multiply by the number of outer iterations (n - 1). This gives a clean upper bound.
Bubble sort compares adjacent elements and swaps them if they are out of order, repeating until the list is sorted.
Counting comparisons: On each pass i (from 1 to n - 1), the inner loop makes n - i comparisons. The total is:
Sum from i = 1 to n - 1 of (n - i) = (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2 = (1/2)n^2 - (1/2)n
Tight Big-O bound: O(n^2). The dominant term is n^2; the linear term and the 1/2 constant are absorbed.
This is the comparison count for the standard, unoptimised version. An optimised bubble sort that stops early when no swaps occur can finish in O(n) on an already-sorted input, but the worst case remains O(n^2).
The three components
Base case: Verify the proposition P(n) for the smallest value, usually n = 1.
Inductive hypothesis: Assume P(k) is true for some arbitrary positive integer k.
Inductive step: Using the assumption that P(k) holds, prove that P(k + 1) must also hold.
If both the base case and the inductive step are valid, the proposition holds for every positive integer.
Worked example: 4^n - 1 is divisible by 3
Let P(n) denote "4^n - 1 is divisible by 3."
Base case: P(1): 4^1 - 1 = 3, which is divisible by 3. (Note: you substitute n = 1 into the expression, giving 4^1 - 1, not 4^0 - 1.)
Inductive hypothesis: Assume P(k) is true, i.e. 4^k - 1 is divisible by 3.
Inductive step: Show P(k + 1): 4^(k+1) - 1 = 4 * 4^k - 1 = 4(4^k - 1) + 3. By the hypothesis, 4^k - 1 is divisible by 3, so 4(4^k - 1) is divisible by 3. Adding 3 (also divisible by 3) keeps the sum divisible by 3.
Identifying the inductive hypothesis
The inductive hypothesis is P(k): the assumption you make before proving P(k) leads to P(k + 1). It is not P(1) (that is the base case), and it is not P(k) -> P(k + 1) (that is the entire inductive step, not just the hypothesis within it).
Students often count only the outer loop iterations and forget that the inner loop count varies. A halving inner loop contributes log(i) per iteration, not a constant.
Assuming bubble sort is O(n) because "it just compares neighbours." The nested structure means the total comparisons are quadratic.
Confusing the base case with n = 0 when the proposition is stated for all positive integers. If P(n) is "4^n - 1 is divisible by 3 for all positive integers," the base case is n = 1 (giving 4^1 - 1 = 3), not n = 0.
Mixing up the inductive hypothesis with the inductive step. The hypothesis is the assumption P(k); the step is the full argument that P(k) implies P(k + 1). Exam questions that list both P(k) and P(k) -> P(k + 1) as options are testing exactly this distinction.
⚠️ Expect code-reading questions where you must trace loop variables and determine the tight Big-O bound. Halving loops (j = j/2) are a favourite because they produce the less-obvious O(n log n) rather than O(n^2).
⚠️ Bubble sort's O(n^2) is a standard reference point. Know the summation that produces it.
⚠️ Induction questions often test whether you can identify the correct base case and distinguish the inductive hypothesis from the inductive step.
⚠️ Some quiz platforms mark P(n) as incorrect when P(k) is the expected answer for "inductive hypothesis." Conceptually P(n) works, but exam grading may require P(k) specifically.
True or false: A loop that halves its variable each iteration runs O(n) times. (False, it runs O(log n) times.)
Fill in the blank: The total comparisons in bubble sort on a list of n elements is ___. (n(n-1)/2, which is O(n^2).)
True or false: The inductive hypothesis is P(k) -> P(k+1). (False, that is the inductive step. The hypothesis is P(k) alone.)
What is the base case for proving "4^n - 1 is divisible by 3" for all positive integers? (n = 1: 4^1 - 1 = 3.)
True or false: If the outer loop runs n times and the inner loop runs log(i) times, the total is O(n^2). (False, it is O(n log n).)
Q: Given the nested loop where the outer runs i from 1 to n-1 and the inner halves j starting at i, what is the tight Big-O bound on the print statement?
A: O(n log n). The inner loop runs floor(log i) times per outer iteration. Summing floor(log i) from i = 1 to n - 1 and bounding each by log n gives at most (n - 1) * log n, which is O(n log n).
Q: Why is the tightest Big-O for bubble sort O(n^2) and not O(n)?
A: The nested loops produce a triangular sum: (n - 1) + (n - 2) + ... + 1 = n(n - 1)/2. The dominant term is n^2/2, so the complexity is O(n^2).
Q: In an induction proof of P(n) for all positive integers, what do you assume in the inductive step?
A: You assume P(k) is true for some arbitrary positive integer k (the inductive hypothesis), then use that assumption to prove P(k + 1).
Q: What is the correct base case for proving 4^n - 1 is divisible by 3?
A: Substitute n = 1: 4^1 - 1 = 3, which is divisible by 3. The base case is not n = 0, because the proposition is stated for positive integers.
Q: A quiz lists these as choices for "the inductive hypothesis": P(k), P(1), P(n), P(k) -> P(k+1). Which is correct?
A: P(k). P(1) is the base case, and P(k) -> P(k + 1) is the entire inductive step. P(n) is conceptually equivalent to P(k) but may not be accepted by automated grading.
Nested loop analysis is the foundation for understanding every comparison-based sorting algorithm (selection sort, insertion sort, merge sort). The halving-loop pattern reappears in binary search and divide-and-conquer recurrences. Mathematical induction is the standard proof technique for verifying summation formulas (like the closed form for 1 + 2 + ... + n), correctness of recursive algorithms, and properties of trees and graphs.
Nested loop analysis, halving loop, logarithmic inner loop, bubble sort complexity, comparison count, triangular sum, mathematical induction, base case, inductive hypothesis, inductive step, proof by induction, P(k), P(k+1), 4^n - 1 divisible by 3, CS182, Purdue, foundations of computer science, algorithm analysis, loop invariant, sorting algorithm complexity