Difficulty: Intermediate–Advanced | Prerequisites: Asymptotic Notation (Big-O, Big-Omega, Big-Theta) study notes, basic calculus (Taylor series).
Once you have the definitions of O, Ω, and Θ, the next step is learning to manipulate them algebraically so you can analyse real expressions without grinding through the formal definition every time. This material also introduces key tools for bounding summations and approximating factorials, which appear constantly in algorithm analysis. You should be comfortable with the three notations and their formal definitions before tackling this.
Big-O has algebraic rules (sum, product, constant factor, nesting) that let you simplify expressions quickly. Summations like Σi and Σi² have known asymptotic bounds. Stirling’s formula approximates n! and is essential for analysing algorithms that involve permutations or combinatorics. Taylor expansions let you use O notation to capture the error in approximations.
O manipulation (Big-O algebra)
A set of identities that let you combine, simplify, and reason about Big-O expressions without returning to the formal ε-n₀ definition each time.
Think of it as: arithmetic rules for growth rates, the same way you have rules for adding fractions.
Sum rule for Big-O
O(f(n)) + O(g(n)) = O(|f(n)| + |g(n)|), which in practice equals O(max(|f(n)|, |g(n)|)). The larger-growing term dominates.
In simple terms, this means: when you add two things together, the faster-growing one wins.
Product rule for Big-O
O(f(n)) · O(g(n)) = O(f(n) · g(n)). Growth rates multiply.
In simple terms, this means: if you nest two operations, you multiply their complexities.
Stirling’s formula / Stirling’s approximation
An approximation for the factorial: n! ≈ √(2πn) · (n/e)ⁿ · (1 + O(1/n)). Becomes more accurate as n grows.
Think of it as: a way to convert the unwieldy n! into a closed-form expression you can actually work with in asymptotic analysis.
Taylor expansion (with Big-O remainder)
A way of writing a function as a polynomial plus an error term expressed in Big-O. For example, eˣ = 1 + x + x²/2 + x³/6 + O(x⁴) as x → 0.
In simple terms, this means: you approximate a function by its first few terms and bundle everything you are ignoring into an O(...) remainder.
These rules follow directly from the definition and save you from reproving bounds every time.
f(n) = O(f(n)). Any function is its own upper bound.
c · O(f(n)) = O(f(n)), for any constant c. Constant factors vanish.
O(O(f(n))) = O(f(n)). Nesting Big-O collapses.
O(f(n)) · O(g(n)) = O(f(n) · g(n)). Products distribute.
O(f(n) · g(n)) = f(n) · O(g(n)). You can pull a known function out of the O.
O(f(n)) + O(g(n)) = O(|f(n)| + |g(n)|). Sums combine.
nᵐ = O(nᵐʹ) whenever m ≤ mʹ. Lower powers are absorbed by higher ones.
A useful derived identity: O(f(n))² = O(f(n)²). This lets you write O(log n)² instead of the more cluttered O((log n)²).
Caution on exponents outside O: O(log n)⁻¹ is not legitimate shorthand for O((log n)⁻¹). The set 1/O(log n) is neither a subset nor a superset of O(1/log n). Restrict exponents outside O to positive values.
Σ i from 1 to n = Θ(n²)
The exact value is n(n+1)/2, which is ≥ n²/2 = Ω(n²) and ≤ n² = O(n²). So the sum of the first n integers is Θ(n²).
Σ i² from 1 to n = Θ(n³)
Upper bound: each i² ≤ n², so the sum ≤ n² · n = n³.
Lower bound: take only the top half of the terms (i from n/2 to n). Each i² ≥ (n/2)² = n²/4, and there are n/2 such terms, so the sum ≥ (n/2) · (n²/4) = n³/8 = Ω(n³).
Simple bounds on n!
Upper bound: n! = 1 · 2 · ... · n ≤ nⁿ (every factor is at most n).
Lower bound: n! = 1 · 2 · ... · (n/2) · ... · n ≥ (n/2)^(n/2) (the top half of the factors are each at least n/2).
Stirling’s formula
n! = √(2πn) · (n/e)ⁿ · (1 + O(1/n))
This gives a very accurate estimate for large n and is the standard tool for converting factorials into expressions you can compare asymptotically.
Taylor series can be truncated, with the remainder captured in Big-O notation (as x → 0):
eˣ = 1 + x + x²/2 + x³/6 + O(x⁴)
ln(1 + x) = x – x²/2 + x³/3 + O(x⁴)
1/(1 – x) = 1 + x + x² + x³ + O(x⁴)
(1 + x)ᵅ = 1 + αx + (α choose 2)x² + O(x³) (generalised binomial / Newton)
These are used in worked examples to evaluate expressions like (n–1)! by substituting x = 1/n into the relevant series and collecting the O terms.
Apply Stirling to (n–1)! by writing √(n–1) = √n · (1 – 1/(2n) + O(1/n²)) and (n–1)ⁿ⁻¹ = nⁿ⁻¹ · (1–1/n)ⁿ · 1/(1–1/n), where (1–1/n)ⁿ → e⁻¹. The result:
(n–1)! = √(2πn) · (n/e)ⁿ⁻¹ · (1/e) · (1 + O(1/n))
Using the Taylor expansion of n^(1/n) = exp((ln n)/n) = 1 + (ln n)/n + O((ln n)²/n²), you get:
n(ⁿ√n – 1) = ln n + O((ln n)²/n)
f(n) = O(f(n))c \cdot O(f(n)) = O(f(n)), \quad c \text{ constant}O(f(n)) + O(g(n)) = O(|f(n)| + |g(n)|)O(f(n)) \cdot O(g(n)) = O(f(n) \cdot g(n))n^m = O(n^{m'}) \quad \text{when } m \le m'\sum_{i=1}^{n} i = \frac{n(n+1)}{2} = \Theta(n^2)\sum_{i=1}^{n} i^2 = \Theta(n^3)n! = \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \left(1 + O\!\left(\frac{1}{n}\right)\right)e^x = 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + O(x^4)\ln(1+x) = x - \frac{x^2}{2} + \frac{x^3}{3} + O(x^4)\frac{1}{1-x} = 1 + x + x^2 + x^3 + O(x^4)(1+x)^\alpha = 1 + \alpha x + \binom{\alpha}{2} x^2 + O(x^3)Students treat O(log n)² as ambiguous. It is not: it means O((log n)²). The notation O(log² n) is the one to avoid, because some authors read it as O(log(log n)). Stick with O(log n)² or O((log n)²).
Students try to use negative exponents outside O, writing O(log n)⁻¹ as shorthand for O(1/log n). This is an abuse of notation. The set 1/O(log n) is not the same set as O(1/log n), so the shorthand breaks.
Students apply the sum rule and keep both terms, writing O(n) + O(n²) = O(n + n²). While correct, this is not simplified. The result should be O(n²), since n² dominates.
Students forget that Stirling’s formula has an error term, (1 + O(1/n)). For exact asymptotic work, this term matters. Dropping it silently can lose marks in a proof.
⚠️ You will almost certainly be asked to simplify an expression using the O manipulation rules. Know them cold.
⚠️ Summation bounds (Σi = Θ(n²), Σi² = Θ(n³)) come up when analysing nested loops. The "top half" trick for proving the lower bound of Σi² is a technique worth memorising.
⚠️ Stirling’s formula is the standard way to handle n! in complexity proofs. Expect it on any exam that covers combinatorial algorithms, sorting lower bounds, or counting arguments.
⚠️ Taylor expansion questions test whether you can substitute, expand, and collect O terms cleanly. The (n–1)! worked example is a classic pattern: rewrite in terms of 1/n, expand each piece, multiply, and simplify.
True or false: O(n) + O(n³) = O(n³). True. The cubic term dominates.
True or false: 5 · O(n²) = O(5n²). True, but misleading. Both simplify to O(n²). The constant 5 is absorbed.
Fill in the blank: Σ i from 1 to n = Θ(___). n².
True or false: O(log n)⁻¹ is a valid use of Big-O notation. False. Negative exponents outside O are not permitted.
Fill in the blank: Stirling’s formula says n! ≈ √(2πn) · (___)ⁿ. (n/e).
Q: Simplify (1/3)n³ + (1/2)n² + (1/6)n using the O manipulation rules.
A: Each term is O(n³), since n² = O(n³) and n = O(n³). By the sum rule, the entire expression is O(n³) + O(n³) + O(n³) = O(n³). Alternatively, recognise it as a polynomial with positive leading coefficient 1/3, so by the polynomial theorem, it is Θ(n³).
Q: Prove that Σ i² from 1 to n = Θ(n³).
A: Upper bound: Σ i² ≤ n² · n = n³, so Σ i² = O(n³). Lower bound: take only terms from i = n/2 to n. There are n/2 such terms, each at least (n/2)² = n²/4, so Σ i² ≥ (n/2)(n²/4) = n³/8 = Ω(n³). Both bounds match, so Σ i² = Θ(n³).
Q: Using Stirling’s formula, what is the asymptotic growth rate of n!?
A: n! = Θ(√n · (n/e)ⁿ). It grows faster than any exponential cⁿ (for fixed c) but slower than nⁿ.
Q: A program has two sequential loops: the first runs in O(n²) and the second in O(n log n). What is the overall running time?
A: O(n²). By the sum rule, O(n²) + O(n log n) = O(n²), since n² dominates n log n.
Q: What is the first-order Taylor expansion of eˣ around x = 0, with its remainder in Big-O?
A: eˣ = 1 + x + O(x²). The O(x²) term captures everything from the x²/2 term onward.
The O manipulation rules underpin every complexity proof you will write in this course and beyond. Summation bounds feed directly into loop analysis: any time you see a for-loop whose body cost changes with the index, you are summing a series. Stirling’s formula is essential for the information-theoretic lower bound on comparison sorting (the log(n!) = Θ(n log n) argument). Taylor expansions with O remainders reappear in numerical analysis, probability, and anywhere you approximate a function locally.
Big-O manipulation, O algebra, sum rule, product rule, constant factor rule, summation bounds, sum of first n integers, sum of squares, factorial approximation, Stirling’s formula, Stirling’s approximation, Taylor expansion, Taylor series, Big-O remainder, asymptotic expansion, n factorial, growth rate, CS 182, Purdue, Foundations of Computer Science, loop analysis, nested loops, polynomial simplification, O(n²), O(n³), O(log n), sorting lower bound