Source: CS 18200 Foundations of Computer Science, Purdue University
Tags: big-O notation, asymptotic analysis, growth of functions, witnesses, algorithm runtime, nested loops, direct proof, proof by contradiction, even odd parity, rational irrational proof
Difficulty: Intermediate
Prerequisites: Functions and summation formulas (see Sets and Functions notes). Basic comfort with algebraic manipulation and logarithm rules.
Growth of functions (big-O analysis) is how computer scientists compare algorithms without getting bogged down in hardware specifics. Instead of asking "how many seconds does this take?", you ask "how does the running time scale as the input grows?" This is arguably the most practically useful topic in the entire course, since every technical interview and every systems design decision relies on it. Proof techniques are the tools that let you make these claims rigorously, and they recur throughout mathematics and computer science. Direct proofs, proofs by contradiction, and proofs by contrapositive are the workhorses.
Big-O notation captures the upper bound on a function's growth rate, ignoring constants and lower-order terms. You prove a big-O bound by finding witnesses (constants c and k). Analysing code means counting iterations of the dominant loop structure. Proof techniques (direct, contradiction, contrapositive) let you establish mathematical facts, and parity arguments (even/odd) are a common building block.
Big-O notation, O(g(n))
f(n) is O(g(n)) if there exist positive constants c and k such that f(n) ≤ c · g(n) for all n > k. In simple terms, past some threshold, f grows no faster than a constant multiple of g.
Witnesses (c and k)
The specific constants that prove a big-O claim. c is the multiplier; k is the threshold beyond which the inequality holds. Finding witnesses is how you formally justify a big-O bound.
Dominant term
The term in a function that grows fastest as n increases. All other terms become negligible. For f(n) = 2n² + n, the dominant term is 2n².
Logarithm identity: 2^(log₂ n) = n
This identity is essential for simplifying expressions that mix exponentials and logarithms. It comes up frequently in big-O problems.
Direct proof
Assume the hypothesis is true, then use definitions and algebraic manipulation to derive the conclusion. The most common and straightforward proof technique.
Proof by contradiction
Assume the statement you want to prove is false, then derive a logical impossibility (a contradiction). Since the assumption led to nonsense, the original statement must be true.
Proof by contrapositive
Instead of proving p → q directly, prove ¬q → ¬p, which is logically equivalent. Useful when the negation of the conclusion gives you something concrete to work with.
Even integer
An integer n is even if n = 2k for some integer k.
Odd integer
An integer n is odd if n = 2k + 1 for some integer k.
Rational number
A number that can be expressed as a/b where a, b are integers and b ≠ 0.
Irrational number
A real number that cannot be expressed as a ratio of two integers.
The task: given f(n), find c, k, and g(n) such that f(n) ≤ c · g(n) for all n > k.
Worked example: Show f(n) = 2n² + n is O(n²).
For n ≥ 1, we know n ≤ n². So 2n² + n ≤ 2n² + n² = 3n².
Witnesses: c = 3, k = 1, g(n) = n².
Verification: for all n > 1, 2n² + n < 3n². Done.
The trick is always to bound the lower-order terms by the dominant term. If you have a sum of terms, replace each smaller term with something no larger than the biggest term, then factor.
Sometimes the expression looks complicated but simplifies using identities.
Worked example: f(n) = 2^(log₂ n) · n² + 3n² log₂ n + n − 17.
Simplify: 2^(log₂ n) = n. So the first term becomes n · n² = n³.
The remaining terms: 3n² log₂ n grows slower than n³ (since log₂ n grows slower than n), and n − 17 is negligible.
Therefore f(n) is O(n³).
Count iterations of the innermost operations in terms of the input size variables.
Worked example:
a = 1
for i = 1 to n // runs n times
a = a + 1
endfor
for i = 1 to n // runs n times
for j = 1 to m // runs m times per iteration of i
a = a + i*j
endfor
a = a / 2
endfor
First loop: O(n).
Second loop: the outer loop runs n times, and for each iteration the inner loop runs m times. That is O(n · m) = O(nm).
The division a = a / 2 runs once per outer iteration, contributing O(n), which is absorbed by O(nm).
Total: O(n) + O(nm) = O(nm), since nm dominates n (assuming m ≥ 1).
Key principle: when you have sequential blocks of code, add their complexities. When you have nested loops, multiply. The largest term wins.
Worked example: Prove that for every integer n, if n is even, then 3n² + 2n + 7 is odd.
Assume n is even. By definition, n = 2k for some integer k.
Substitute: 3(2k)² + 2(2k) + 7 = 12k² + 4k + 7.
Rewrite 7 as 6 + 1: 12k² + 4k + 6 + 1 = 2(6k² + 2k + 3) + 1.
Let m = 6k² + 2k + 3. Since k is an integer, m is an integer.
The expression equals 2m + 1, which is odd by definition. ∎
The pattern: substitute the definition of even (n = 2k), expand, rearrange into the form 2m + 1, and confirm m is an integer.
Worked example: Prove that the product of a nonzero rational number and an irrational number is irrational.
Let p ∈ ℚ (nonzero) and m ∈ ℝ − ℚ.
Assume for contradiction that m · p ∈ ℚ.
Since p is rational, p = a/c for integers a, c with c ≠ 0.
Since m · p is rational, m · p = b/d for integers b, d with d ≠ 0.
Then m = (b/d) / (a/c) = bc / (ad). Since products and quotients of integers (with nonzero denominator) are rational, m is rational.
This contradicts our assumption that m is irrational.
Therefore m · p is irrational. ∎
The structure: assume the negation, use definitions to express everything as ratios of integers, and show the irrational number would have to be rational, which is the contradiction.
Big-O definition: f(n) ∈ O(g(n)) ⟺ ∃c > 0, ∃k > 0 such that ∀n > k, f(n) ≤ c · g(n)
Common growth hierarchy (slowest to fastest): O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
Logarithm identity: 2^(log₂ n) = n
Even definition: n = 2k, k ∈ ℤ
Odd definition: n = 2k + 1, k ∈ ℤ
Big-O analysis is how engineers choose between sorting algorithms (O(n log n) merge sort vs. O(n²) insertion sort), decide whether a database query will scale, and estimate cloud computing costs. Proof by contradiction is used throughout security and cryptography to show that breaking an encryption scheme would require solving a problem believed to be computationally hard.
Students think big-O means "approximately equal to." It does not. Big-O is an upper bound. Saying f(n) is O(n³) does not mean f(n) grows like n³; it means f(n) grows no faster than n³. A function that is O(n) is also O(n²), though the tighter bound is more useful.
Students forget that constants do not matter in big-O. 1000n and 3n are both O(n). This surprises students who think 1000n should be "bigger" in some sense, and in practice it is slower for small inputs, but big-O concerns the growth rate, not the absolute size.
In parity proofs, students sometimes assume n is a natural number when the problem says integer. An even integer can be negative (n = −4 is even).
In proofs by contradiction, students sometimes state the contradiction but forget to explain why it is a contradiction. Always name the two conflicting facts explicitly.
⚠️ Finding witnesses (c and k) for big-O is a staple exam question. Show the algebra that bounds f(n) by c · g(n).
⚠️ Simplifying expressions with logarithms and exponents (like 2^(log₂ n) = n) before giving the big-O bound is tested frequently.
⚠️ Loop analysis questions require you to identify which loops are nested (multiply) and which are sequential (add).
⚠️ Direct proofs about parity follow a rigid template: state the definition, substitute, rearrange, conclude. Skipping the "m is an integer" step loses marks.
⚠️ Proof by contradiction requires you to clearly state your assumption, derive the contradiction, and name it. Incomplete contradictions receive partial credit at best.
True or false: If f(n) is O(n²), then f(n) is also O(n³).
True. O(n²) ⊂ O(n³), because n² ≤ n³ for n ≥ 1.
Fill in the blank: 2^(log₂ n) = ___.
n.
True or false: A for loop running from 1 to n inside another for loop running from 1 to n gives O(n) runtime.
False. Nested loops multiply: the runtime is O(n²).
Fill in the blank: To prove a number is odd, show it can be written as 2m + 1 where m is ___.
An integer.
True or false: In a proof by contradiction, you assume the statement you want to prove is true.
False. You assume it is false (negate the conclusion or the entire statement) and derive a contradiction.
Q: Give witnesses to show that f(n) = 5n³ + 2n² + n is O(n³).
A: For n ≥ 1, 2n² ≤ 2n³ and n ≤ n³. So f(n) ≤ 5n³ + 2n³ + n³ = 8n³. Witnesses: c = 8, k = 1.
Q: What is the big-O runtime of the following code?
for i = 1 to n
for j = 1 to n
for k = 1 to n
x = x + 1
A: Three nested loops, each running n times. Runtime is O(n³).
Q: Prove that for every integer n, if n is odd, then n² is odd.
A: Let n be odd. Then n = 2k + 1 for some integer k. So n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1. Let m = 2k² + 2k, which is an integer. Thus n² = 2m + 1, which is odd.
Q: Prove by contradiction that √2 is irrational. (Classic companion to the midterm's rational-times-irrational proof.)
A: Assume √2 = a/b in lowest terms (a, b integers, b ≠ 0). Then 2 = a²/b², so a² = 2b². This means a² is even, so a is even (since the square of an odd number is odd). Write a = 2k. Then 4k² = 2b², giving b² = 2k², so b is also even. But both a and b being even contradicts a/b being in lowest terms. Therefore √2 is irrational.
Big-O analysis builds directly on the summation skills from the Functions topic and connects forward to algorithm design and analysis in later CS courses. The proof techniques here (direct, contradiction, contrapositive) are the same tools used for mathematical induction, which is typically the next major proof topic in CS 18200. Parity arguments show up again in number theory and in proofs about graph colouring (bipartite graphs, for instance, require reasoning about even and odd cycle lengths).
big-O notation, asymptotic analysis, upper bound, growth of functions, witnesses c and k, algorithm complexity, runtime analysis, nested loops, sequential loops, dominant term, logarithm identities, direct proof, proof by contradiction, proof by contrapositive, even integer, odd integer, parity proof, rational number, irrational number, product of rational and irrational, CS 18200, discrete math proofs, Purdue, foundations of computer science