Difficulty: Intermediate | Prerequisites: Discrete maths basics, logarithm properties, summation notation.
Asymptotic notation is the language computer scientists use to describe how algorithms scale. Rather than timing code on a particular machine, Big-O (and its cousins Omega and Theta) give a machine-independent way to classify growth rates. This material sits at the heart of every algorithms course and will reappear whenever you analyse sorting, searching, graph traversal, or any data-structure operation. You should already be comfortable with logarithms (especially base 2), basic algebra of exponents, and the idea that some functions grow faster than others.
Big-O captures the worst-case upper bound on how a function grows, ignoring constants and lower-order terms. Omega is the mirror (lower bound), and Theta means both bounds match. To classify an expression, strip constants, keep only the dominant term, and compare it against the target class, using formal definitions (witness C and threshold k) when the answer is not obvious.
Big-O, O(g(n))
A function 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, f grows no faster than g once n is large enough.
Big-Omega, Ω(g(n))
A function f(n) is Ω(g(n)) if there exist positive constants C and k such that f(n) >= C * g(n) for all n > k. Think of it as the lower-bound counterpart to Big-O: f grows at least as fast as g.
Big-Theta, Θ(g(n))
A function f(n) is Θ(g(n)) if it is both O(g(n)) and Ω(g(n)). In simple terms, f and g grow at the same rate, up to constant factors.
Dominant term
The term in an expression that grows fastest as n increases. When classifying Big-O, every other term can be dropped because the dominant term eventually dwarfs them.
Witness constants (C and k)
The specific values of C (the multiplier) and k (the threshold) that satisfy the Big-O (or Omega) definition for a given pair of functions. You do not need unique witnesses; you just need to show at least one valid pair exists (or prove none can).
(n + 1)! = O(n!) is false. Since (n + 1)! = (n + 1) * n!, dividing both sides by n! gives n + 1, which grows without bound. No fixed constant C can keep (n + 1)! <= C * n! for all large n, because you would need n + 1 <= C, which eventually fails.
n! = O((n + 1)!) is true. Because n! <= 1 * (n + 1)! for every n > 1 (just pick C = 1), the definition is satisfied directly.
The key intuition: multiplying by an ever-growing factor (n + 1) pushes the larger factorial into a strictly higher growth class. The relationship is one-directional.
The strategy: simplify each expression, identify the dominant term, and check whether it is bounded above by some constant times n.
Set 1 (all logs are base 2)
n/125 - 15 log n: The dominant term is n/125, which is linear. The log n term is lower-order. Since n/125 <= n, this is O(n). Correct.
sqrt(16n + 32n) + log(2^(4n)): Simplifies to 4sqrt(n) + 32n + 4n log 2. For large n, 4sqrt(n) is negligible next to 36n. Upper-bounded by 40n, so O(n). Correct.
16n + n^2/16: The n^2 term dominates. n^2 grows faster than n, so this is not O(n).
12 log(n^4): Equals 48 log n. Logarithmic functions grow slower than linear, so 48 log n <= 48n for all n > 1. O(n). Correct.
Set 2
14 log(n^14): Equals 196 log n. Logarithmic, so O(n). Correct.
n^5 / 3125 + 3125n: The n^5 term dominates. Not O(n).
sqrt(25n) + 5n log(2^(2n)): Simplifies to 5*sqrt(n) + 10n^2. The n^2 term dominates. Not O(n).
n/67890 + 12345 log(n): Both terms are bounded by linear functions. n/67890 + 12345 log(n) <= n + 12345n = 12346n. O(n). Correct.
3^n = O(2^n) is false. Dividing both sides of 3^n <= C * 2^n by 2^n gives (3/2)^n <= C. Since (3/2)^n grows without bound, no constant C works.
2^n = O(3^n) is true. (2/3)^n <= 1 for all n > 1, so 2^n <= 1 * 3^n. The smaller base is always upper-bounded by the larger base.
log n = O(log log n) is false. Assuming log n <= C * log log n implies n <= (log n)^C. But linear functions outgrow any fixed power of a logarithm, so this breaks for large n.
n / log n = O(n log n) is true. Since n / log n <= n <= n log n for all n > 2, the bound holds with C = 1.
The rule of thumb for exponentials: a larger base always dominates a smaller base. For logarithms: log log n grows more slowly than log n, which grows more slowly than any positive power of n.
Worked example: f(n) = 4n log(n^2) + 3*sqrt(n)
First simplify: 4n log(n^2) = 8n log n, so f(n) = 8n log n + 3*sqrt(n).
Upper bound: 8n log n + 3*sqrt(n) <= 11n log n for all large n, so f(n) = O(n log n).
Lower bound: 8n log n <= f(n), so f(n) = Ω(n log n).
Tight bound: Both directions match, so f(n) = Θ(n log n).
Also O(n^2)? Yes, because n log n = O(n^2), and Big-O is not required to be tight.
Ω(n^2) or Ω(n^1.5)? No to both. n^2 and n^1.5 both grow faster than n log n, so f(n) cannot be lower-bounded by either.
True/false: n * a^(log_a n) = O(n log n) for all a in N - {0, 1}
False. a^(log_a n) = n by the definition of logarithms. So n * a^(log_a n) = n^2, which grows faster than n log n.
f(n) = O(g(n)) \iff \exists\, C > 0,\; k \geq 0 : f(n) \leq C \cdot g(n) \;\forall\, n > kf(n) = \Omega(g(n)) \iff \exists\, C > 0,\; k \geq 0 : f(n) \geq C \cdot g(n) \;\forall\, n > kf(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ and } f(n) = \Omega(g(n))Growth-rate hierarchy (slowest to fastest):
1, log log n, log n, sqrt(n), n, n log n, n^2, n^3, ..., 2^n, 3^n, ..., n!, (n+1)!
Useful log identities (base 2 throughout):
log(n^k) = k log n
log(2^n) = n
a^(log_a n) = n
Students often assume Big-O must be a tight bound. It does not have to be. Saying f(n) = O(n^2) when f(n) = n is technically correct, just not the tightest statement you could make.
Confusing the direction of factorial relationships. (n + 1)! is strictly larger than n!, so n! = O((n + 1)!) works but the reverse does not. The extra factor of (n + 1) grows without bound.
Treating constants inside logarithms as though they change the growth class. log(n^4) = 4 log n, which is still O(log n). A constant exponent inside a log becomes a constant multiplier outside.
Forgetting that sqrt(n) is sub-linear. sqrt(n) grows slower than n, so terms like 4*sqrt(n) are absorbed by any linear term when classifying O(n).
Assuming (3/2)^n is bounded. Any base greater than 1, raised to the power n, grows without bound. This is the core reason 3^n is not O(2^n).
⚠️ Expect questions that ask you to prove a Big-O claim by supplying explicit C and k values, or to disprove one by showing no such pair can exist.
⚠️ "Select all that are O(n)" is a recurring format. The trick is always: simplify, find the dominant term, compare to n.
⚠️ Theta questions test whether you check both directions (upper and lower bound), not just one.
⚠️ True/false statements involving a^(log_a n) are designed to catch students who do not simplify the expression before judging it.
True or false: 5^n = O(4^n). (False, larger base dominates.)
True or false: n/1000 + log n is O(n). (True, both terms are at most linear.)
Fill in the blank: f(n) = Θ(g(n)) means f(n) is both ___ and ___. (O(g(n)) and Ω(g(n)).)
True or false: log(n^100) is O(n). (True, 100 log n is still logarithmic.)
True or false: n! = O(n^n). (True, every factor of n! is at most n.)
Q: Prove or disprove: (n + 1)! = O(n!)
A: Disprove. Suppose (n + 1)! <= C * n! for all n > k. Dividing both sides by n! gives n + 1 <= C, which fails for any n > C - 1. Therefore (n + 1)! is not O(n!).
Q: Is sqrt(25n) + 5n log(2^(2n)) in O(n)?
A: No. Simplify: 5sqrt(n) + 5n * 2n = 5sqrt(n) + 10n^2. The n^2 term dominates, so this grows faster than linear.
Q: Given f(n) = 4n log(n^2) + 3*sqrt(n), state its tightest asymptotic class using Theta notation.
A: f(n) = Θ(n log n). Simplify to 8n log n + 3*sqrt(n). The 8n log n term dominates sqrt(n), and you can show both O(n log n) and Ω(n log n) with appropriate constants.
Q: True or false: n * a^(log_a n) = O(n log n) for a >= 2.
A: False. a^(log_a n) simplifies to n, so the expression equals n^2, which grows faster than n log n.
Q: Which of the following is not O(n): (i) n/125 - 15 log n, (ii) 16n + n^2/16, (iii) 12 log(n^4)?
A: (ii). The n^2/16 term means the expression is Θ(n^2), not O(n).
Asymptotic notation feeds directly into algorithm analysis: every time you count operations in a loop or a recursive call, you express the result in Big-O (or Theta). This connects to sorting algorithm complexity (bubble sort is O(n^2), merge sort is O(n log n)), divide-and-conquer recurrences, and graph algorithm costs. It also appears in data-structure analysis when you compare, say, array lookup O(1) against linked-list traversal O(n).
Big-O notation, asymptotic analysis, upper bound, lower bound, tight bound, Big-Omega, Big-Theta, growth rate, dominant term, witness constants, O(n), O(n log n), O(n^2), factorial growth, exponential growth, logarithmic growth, CS182, Purdue, foundations of computer science, algorithm complexity, order of growth, asymptotic equivalence