Difficulty: Intermediate | Prerequisites: Basic algebra, exponent rules, logarithms, summation notation.
Algorithm analysis is how computer scientists measure the efficiency of code without running it. Big-O notation gives you a way to describe how the number of operations grows as the input size increases. This week also covers recurrence relations (formulas that define a sequence in terms of its previous values) and comparing growth rates of functions. These ideas appear in every algorithms course and every technical interview. You should be comfortable with exponents, logarithms, and basic summation before diving in.
Big-O notation captures the dominant term that controls a function's growth as n gets large, ignoring constants and lower-order terms. Recurrence relations define sequences where each term depends on the previous one (like compound interest). When comparing two functions' growth rates, the one with the smaller exponent or slower-growing dominant term wins for large n.
Big-O notation, O(f(n))
A function 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₀. It describes an upper bound on growth rate.
Think of it as: "this function grows no faster than f(n), once n is large enough."
Same order (Θ notation, informally)
Two functions f(n) and g(n) are of the same order if f(n) is O(g(n)) and g(n) is O(f(n)). Their dominant terms match.
In simple terms, they grow at the same rate for large n, even if their exact values differ.
Dominant term
The term in a sum of functions that grows fastest as n increases. For Big-O purposes, only the dominant term matters.
In simple terms, it is the term that "wins" and dwarfs everything else when n is huge.
Recurrence relation (recursive formula)
A formula that defines each term of a sequence using one or more previous terms, plus an initial condition.
Think of it as a rule that says "to get the next value, do this to the current value."
Iteration count
The number of times a loop body executes. For a loop running from i = a to i = b, the iteration count is b – a + 1.
In simple terms, count how many times the loop goes round.
You take a job paying $55,000. Each year you get a raise defined by a rule. Express your salary n years from now as a recurrence.
3% annual raise
Initial condition: a₁ = 55,000
Recurrence: aₙ = aₙ₋₁ + 0.03 · aₙ₋₁ = 1.03 · aₙ₋₁
Closed form: aₙ = 55,000 × 1.03ⁿ⁻¹
This is geometric growth (constant percentage increase each period).
5% annual raise
Initial condition: a₁ = 55,000
Recurrence: aₙ = 1.05 · aₙ₋₁
Closed form: aₙ = 55,000 × 1.05ⁿ⁻¹
Same structure, different growth factor.
$1,000 flat raise plus 2% of previous salary
Initial condition: a₁ = 55,000
Recurrence: aₙ = aₙ₋₁ + 0.02 · aₙ₋₁ + 1,000 = 1.02 · aₙ₋₁ + 1,000
This is a non-homogeneous linear recurrence (it has a constant additive term). Closed-form solutions for these exist but are more involved.
Pattern to recognise: Percentage-only raises give a geometric sequence with ratio (1 + rate). Adding a flat amount makes it non-homogeneous.
Given the algorithm:
t ← 1 for i = n to n² t ← t + 2 × i × t end
Step 1: Count iterations
The loop runs from i = n to i = n². The number of iterations is n² – n + 1.
Step 2: Count operations per iteration
The line t ← t + 2 × i × t contains:
2 multiplications: 2 × i and (result) × t
1 addition: t + (result)
Total: 3 operations per iteration
Step 3: Multiply
Total operations = 3(n² – n + 1) = 3n² – 3n + 3
Step 4: Extract Big-O
The dominant term is 3n². Drop the constant factor: O(n²).
Two algorithms solve the same problem. Algorithm A uses n√n operations. Algorithm B uses n log n operations.
Rewrite n√n as n³ʲ. The exponent 3/2 = 1.5, so n√n grows like n^1.5.
Meanwhile, n log n grows much more slowly. For any ε > 0, n log n is eventually smaller than n^(1+ε). Since 1.5 > 1, the function n√n overtakes n log n and grows faster for large n.
Algorithm B (n log n) uses fewer operations as n grows. This is consistent with the standard growth rate hierarchy: n log n sits between linear and polynomial growth.
Given the list of functions, identify the dominant term of each:
n² + log n: dominant term is n², so order is Θ(n²)
2ⁿ + 3ⁿ: dominant term is 3ⁿ (exponential with larger base wins), so order is Θ(3ⁿ)
100n³ + n²: dominant term is 100n³ = n³, so order is Θ(n³)
n² + 2ⁿ: dominant term is 2ⁿ (exponential beats polynomial), so order is Θ(2ⁿ)
n² + n³: dominant term is n³, so order is Θ(n³)
3n³ + 2ⁿ: dominant term is 2ⁿ (exponential beats polynomial), so order is Θ(2ⁿ)
Same-order pairs:
(100n³ + n²) and (n² + n³): both Θ(n³)
(n² + 2ⁿ) and (3n³ + 2ⁿ): both Θ(2ⁿ)
The key technique: For sums of terms, the dominant term is whichever grows fastest. Exponentials beat polynomials. Among polynomials, higher degree wins. Among exponentials, larger base wins. Constants and lower-order terms vanish in Big-O.
1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < 3ⁿ < n!
This hierarchy is worth memorising. It tells you immediately which term dominates in a sum.
a_n = 1.03 \cdot a_{n-1}, \quad a_1 = 55{,}000a_n = 1.02 \cdot a_{n-1} + 1000, \quad a_1 = 55{,}000\text{Loop iterations: } n^2 - n + 1 \quad \Rightarrow \quad O(n^2)Big-O notation is how engineers decide whether an algorithm will scale. A search engine processing billions of queries cannot use O(n²) where O(n log n) is possible. Recurrence relations model compound interest, population growth, and the running time of recursive algorithms (merge sort's recurrence is T(n) = 2T(n/2) + O(n), which solves to O(n log n)).
Students often forget to count all operations in a loop body. In t ← t + 2 × i × t, there are 2 multiplications and 1 addition, not just 1 operation. Read the expression carefully and count each arithmetic operator.
Students sometimes include the constant term in Big-O. The function 3n² – 3n + 3 is O(n²), not O(3n² – 3n + 3). Big-O strips constants and lower-order terms.
A common error is thinking that n² + 2ⁿ is O(n²). Exponential functions grow faster than any polynomial. The dominant term here is 2ⁿ, not n².
Students confuse "same order" with "same value." Two functions are of the same order if they grow at the same rate (within a constant factor for large n), not if they produce the same output for a given n. 100n³ + n² and n² + n³ have vastly different values for small n, but they are both Θ(n³).
⚠️ Big-O estimation from a code segment is a near-certain exam question. Practise the four-step process: count iterations, count operations per iteration, multiply, extract the dominant term.
⚠️ Know the growth rate hierarchy by heart: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < 3ⁿ < n!
⚠️ "Find pairs of the same order" questions test whether you can identify dominant terms quickly. Exponential always beats polynomial. Larger base beats smaller base.
⚠️ Recurrence relations may appear as "write a recursive formula for..." problems. Know the pattern: percentage growth = multiply by (1 + rate); flat addition = add a constant.
⚠️ Comparing n√n vs n log n: rewrite n√n as n^(3/2) to see immediately that it grows faster than n log n.
True or false: O(3n²) is the same as O(n²). True. Constants are dropped in Big-O.
Fill in the blank: A loop from i = n to i = n² runs ___ iterations. n² – n + 1.
True or false: 2ⁿ + n³ is O(n³). False. The dominant term is 2ⁿ.
True or false: n log n grows faster than n√n for large n. False. n√n = n^(3/2) grows faster.
Fill in the blank: A 3% annual raise on $55,000 gives a recurrence aₙ = ___ · aₙ₋₁. 1.03.
Q: Give the Big-O estimate for the algorithm: for i = n to n², do t ← t + 2 × i × t.
A: The loop runs n² – n + 1 times. Each iteration has 3 operations (2 multiplications, 1 addition). Total = 3(n² – n + 1). Big-O: O(n²).
Q: Which grows faster as n increases: n√n or n log n?
A: n√n = n^(3/2) grows faster. Since 3/2 > 1, it eventually dominates n log n, which grows slower than any n^(1+ε) for ε > 0.
Q: Why are (n² + 2ⁿ) and (3n³ + 2ⁿ) of the same order?
A: In both, 2ⁿ is the dominant term because exponentials grow faster than polynomials. Both are Θ(2ⁿ).
Q: Write a recurrence for salary after n years with a $1,000 raise plus 2% of previous salary, starting at $55,000.
A: a₁ = 55,000; aₙ = 1.02 · aₙ₋₁ + 1,000. This is a non-homogeneous linear recurrence.
Q: A function f(n) = 5n³ + 200n² + log n. What is its Big-O?
A: O(n³). The dominant term is 5n³; the constant 5 and lower-order terms (200n², log n) are dropped.
Big-O notation is foundational for every algorithms course that follows. Recurrence relations connect directly to recursive algorithm analysis (merge sort, quicksort, binary search all have defining recurrences). Growth rate comparisons tie into complexity classes (P, NP) and the question of whether efficient algorithms exist for a given problem. The salary recurrence is a special case of the general first-order linear recurrence, which appears again in differential equations and signal processing.
Big-O notation, asymptotic analysis, growth rate, dominant term, recurrence relation, recursive formula, geometric sequence, compound interest, loop analysis, operation counting, same order, Theta notation, n log n, n root n, exponential vs polynomial, function orders, CS 182, Purdue, discrete mathematics, foundations of computer science, algorithm complexity, time complexity