Key takeaways
- f(n) = O(g(n)) means there are positive constants c and k with f(n) ≤ c·g(n) for every n ≥ k: g bounds f from above, up to a constant factor, eventually.
- To prove a big-O claim, exhibit specific c and k and show the inequality; to disprove one, show no constant can work.
- Big-Omega gives a lower bound and big-Theta a tight bound, both above and below.
- Constants and lower-order terms are dropped: 5n² + 3n + 7 is Θ(n²).
- The common classes, from slowest-growing to fastest, are 1, log n, n, n log n, n², n³, 2ⁿ and n!.
Big-O notation is how computer scientists compare algorithms without timing them on a particular machine. It describes how a cost, usually running time or memory, grows as the input gets larger, and it deliberately ignores constant factors that depend on hardware. In a discrete math course it is treated as what it is underneath: a precise statement with quantifiers, which can be proved and disproved like any other.
The formal definition
NIST's Dictionary of Algorithms and Data Structures gives the formal version:
f(n) = O(g(n)) means there are positive constants c and k such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.
Read it as: eventually (from some k on), f is at most a constant multiple of g. Both qualifiers matter. "Eventually" lets small inputs behave however they like. "A constant multiple" means 100n and n are treated as the same rate of growth.
In quantifier form, f(n) = O(g(n)) is ∃c ∃k ∀n ≥ k (f(n) ≤ c·g(n)). The order of the quantifiers is what forces c and k to be chosen before n, the point stressed in predicates and quantifiers.
Proving a big-O claim
To prove f(n) = O(g(n)), exhibit a c and a k, then verify the inequality.
Claim. n² + 3n + 4 = O(n²).
Proof. For n ≥ 1 we have n ≤ n² and 1 ≤ n², so
n² + 3n + 4 ≤ n² + 3n² + 4n² = 8n².
Take c = 8 and k = 1. ∎
Many other constants also work; NIST's own example notes that n² + 3n + 4 < 2n² once n is larger than 10. Any valid pair proves the claim. The bounding trick, replacing each lower-order term by a multiple of the highest power, works for every polynomial.
Disproving a big-O claim
To show f(n) is not O(g(n)), you must show that no constants work, which is the negation of an existential statement.
Claim. n² is not O(n).
Proof. Suppose there were c and k with n² ≤ cn for all n ≥ k. Dividing by n gives n ≤ c for all n ≥ k. But n = max(k, ⌈c⌉ + 1) is at least k and greater than c, a contradiction. ∎
This is a proof by contradiction, and its structure, "whatever constant you pick, a large enough n beats it", is the template for every disproof.
Big-Omega and big-Theta
| Notation | Meaning | Informally |
|---|---|---|
| f = O(g) | f(n) ≤ c·g(n) eventually | f grows no faster than g |
| f = Ω(g) | f(n) ≥ c·g(n) eventually, for some c > 0 | f grows at least as fast as g |
| f = Θ(g) | Both O(g) and Ω(g) | f and g grow at the same rate |
Big-O alone is only an upper bound, so it can be loose. NIST notes that 3n + 4 is, strictly speaking, O(n²) too, and that big-O is often misused to mean "equal to" rather than "less than". So when "this algorithm is O(n)" is meant as a tight bound, the precise statement is Θ(n).
The rules you actually use
- Drop constant factors: 7n³ is Θ(n³).
- Keep only the fastest-growing term: n³ + 1000n² is Θ(n³).
- Sums of steps add, and the biggest wins: an O(n) step followed by an O(n²) step is O(n²) overall.
- Nested loops multiply: a loop of n iterations containing a loop of n iterations is O(n²).
- Logarithm bases do not matter: log₂ n and log₁₀ n differ by a constant factor, so both are Θ(log n).
The common growth classes
Sedgewick and Wayne's Algorithms observes that, because programs are built from a few structures (statements, conditionals, loops, nesting and method calls), the order of growth of a cost is very often one of just a few functions of the problem size. In order:
| Growth | Name | Typical source |
|---|---|---|
| 1 | Constant | Reading one array entry |
| log n | Logarithmic | Binary search: halving the range each step |
| n | Linear | One pass over the input |
| n log n | Linearithmic | Mergesort: halving, then a linear merge at each level |
| n² | Quadratic | Comparing every pair |
| n³ | Cubic | Checking every triple, as in brute-force 3-sum |
| 2ⁿ | Exponential | Trying every subset |
| n! | Factorial | Trying every ordering |
The jumps are enormous. With n = 1,000, log₂ n is about 10, n² is a million and 2ⁿ has more than 300 digits. NIST's entry draws the practical lesson: quicksort, O(n log n) on average, running on a small desktop computer can beat bubble sort, O(n²), running on a supercomputer if there are a lot of numbers to sort. Sedgewick and Wayne make the same point by replacing a brute-force 3-sum, which uses about N³/2 array accesses, with a method built on mergesort and binary search that runs in time proportional to N² log N.
Where these bounds come from
Running times of recursive algorithms are usually found by setting up and solving recurrence relations: mergesort's T(n) = 2T(n/2) + n solves to Θ(n log n). Average-case running times are expected values over random inputs. And some classical algorithms come with their own analysis; for the Euclidean algorithm, MathWorld reports Lamé's result that the number of steps is at most about five times the number of digits in the smaller number, which is why it is fast even for huge numbers.
Big-O mistakes to avoid
- Treating O as "equals". It is an upper bound; say Θ when you mean tight.
- Letting c depend on n. "f(n) ≤ n · g(n)" is not a big-O bound unless n is part of g.
- Ignoring the "eventually". A bound that fails for small n can still be valid; a bound that fails for infinitely many large n cannot.
- Comparing algorithms only by big-O on small inputs. Constants matter in practice when n is small.
Big-O belongs with the induction and algorithms unit of Discrete Math: Study & Quiz. The app is listed with our education apps, and graph algorithms such as Dijkstra's algorithm come later in the discrete math hub.
Good to know
Frequently asked questions
What does big-O notation mean?
How do you prove that a function is O(n²)?
What is the difference between big-O, big-Omega and big-Theta?
Is O(log n) faster than O(n)?
Sources
- big-O notation (Dictionary of Algorithms and Data Structures) (opens in a new tab)National Institute of Standards and Technology (NIST) — accessed
- Analysis of Algorithms (Algorithms, 4th edition, Sedgewick and Wayne) (opens in a new tab)Princeton University — accessed
- 6.042J Mathematics for Computer Science, Spring 2015: Readings (opens in a new tab)MIT OpenCourseWare — accessed
- Euclidean Algorithm (opens in a new tab)Wolfram MathWorld — accessed
About the author
Reign Creative LLC — The independent app studio that builds the apps covered on this site and publishes every article here. On Google Play it publishes as Reign Collective Apps.
We use AI tools to help research, draft and edit our articles. Each article lists the sources its factual claims rely on, and details about our apps come from their live Google Play listings. No article on this site has been reviewed by an independent expert unless the reviewer is named on it.
No person at Reign Creative LLC has read this article in full. It was published after automated checks and an AI editorial review, which are described in our editorial policy and are not the same as a person reading every sentence.
Spotted an error? Tell us — how corrections are handled is set out in our editorial policy.