Big-O notation (asymptotic upper bound)
Big O classifies the asymptotic upper growth of a runtime or memory function up to a constant factor.
Free to browse · flashcards or a multiple-choice quiz · import from Essential
Formula
n is input size; f(n) and g(n) use the same cost units; c>0 and n0 are constants
Variables & units
| Symbol | Meaning | Unit |
|---|---|---|
| Cost function being analyzed | operations or memory usage | |
| Comparison growth function | same dimension as f | |
| Positive constant factor independent of n | dimensionless | |
| Threshold beyond which the bound holds | problem size |
LaTeX
f(n) \in O(g(n)) \iff \exists c>0,n_0: \forall n\ge n_0,\ |f(n)|\le c|g(n)|
Original schematic by Quanta
Free with a Quanta account. Your download stays ready after registration.
Derivation & background
f(n)∈O(g(n)) means there are constants c>0 and n0 such that |f(n)|≤c|g(n)| for every n≥n0. Constants and lower-order terms are abstracted away, but the cost model still matters: define whether f counts comparisons, memory accesses or another operation. Big O is an upper bound, not necessarily a tight bound or a runtime in seconds. Θ expresses a tight asymptotic order; Ω expresses a lower bound.
Exam blueprint
Validity range
f(n)∈O(g(n)) means there are constants c>0 and n0 such that |f(n)|≤c|g(n)| for every n≥n0. Constants and lower-order terms are abstracted away, but the cost model still matters: define whether f counts comparisons, memory accesses or another operation. Big O is an upper bound, not necessarily a tight bound or a runtime in seconds. Θ expresses a tight asymptotic order; Ω expresses a lower bound.
Derivation steps
Big O classifies the asymptotic upper growth of a runtime or memory function up to a constant factor.
- 1Read the relation from its definition: f(n) \in O(g(n)) \iff \exists c>0,n0: \forall n\ge n0,\ |f(n)|\le c|g(n)|.
- 2Identify the input, requested output and assumptions of the relation.
- 3For n≥1, 3n2+8n+2≤13n2, so this function is O(n2). The statement describes growth, not a number of seconds.
Rearrangements
Defining relation
The equation states the defining relation within its stated domain.
Task variant
Use the example for Big-O notation (asymptotic upper bound) to explain which inputs determine the requested output.
The example connects concrete inputs to its result.
Big O classifies the asymptotic upper growth of a runtime or memory function up to a constant factor.
The relation applies only under its stated assumptions.
Common mistakes
Applying the relation to a different case without checking its stated assumptions.
Check the validity range before substituting values: f(n)∈O(g(n)) means there are constants c>0 and n0 such that |f(n)|≤c|g(n)| for every n≥n0. Constants and lower-order terms are abstracted away, but the cost model still matters: define whether f.
Exam context
- Compare algorithm scaling, estimate behavior for growing inputs and identify likely complexity bottlenecks.
Formula cluster
Algorithm analysis
Big O classifies the asymptotic upper growth of a runtime or memory function up to a constant factor.
Worked example
For n≥1, 3n2+8n+2≤13n2, so this function is O(n2). The statement describes growth, not a number of seconds.
Applications
Compare algorithm scaling, estimate behavior for growing inputs and identify likely complexity bottlenecks.
How do you calculate with Big-O notation (asymptotic upper bound)?
Here is how to work through a typical Big-O notation (asymptotic upper bound) (f(n) ∈ O(g(n))) task step by step:
- 1
Task
Use the example for Big-O notation (asymptotic upper bound) to explain which inputs determine the requested output.
Solution path
The example connects concrete inputs to its result.
Big O classifies the asymptotic upper growth of a runtime or memory function up to a constant factor.
The relation applies only under its stated assumptions.
Frequently asked questions about Big-O notation (asymptotic upper bound)
What does Big-O notation (asymptotic upper bound) describe?+
The relation f(n) \in O(g(n)) \iff \exists c>0,n0: \forall n\ge n0,\ |f(n)|\le c|g(n)| summarizes Big O classifies the asymptotic upper growth of a runtime or memory function up to a constant factor. Read it as a model for defined quantities, not as an automatic claim about every real situation. In the example For n≥1, 3n2+8n+2≤13n2, so this function is O(n2). The statement describes growth, not a number of seconds., symbols are connected to concrete values and the result is interpreted in context. Validity limit: f(n)∈O(g(n)) means there are constants c>0 and n0 such that |f(n)|≤c|g(n)| for every n≥n0. Constants and lower-order terms are abstracted away, but the cost model still matters: define whether f Source: MIT OpenCourseWare, 6.046J Introduction to Algorithms, Lecture 2: “Asymptotic Notation; Recurrences; Substitution, Master Method”.
How should I work through a calculation?+
First write down the requested quantity and all given values with their symbols. Substitute them into the defining relation and check unit consistency. The example For n≥1, 3n2+8n+2≤13n2, so this function is O(n2). The statement describes growth, not a number of seconds. provides a worked check: formula and result must have compatible scale and meaning; round only at the end. Validity limit: f(n)∈O(g(n)) means there are constants c>0 and n0 such that |f(n)|≤c|g(n)| for every n≥n0. Constants and lower-order terms are abstracted away, but the cost model still matters: define whether f Source: MIT OpenCourseWare, 6.046J Introduction to Algorithms, Lecture 2: “Asymptotic Notation; Recurrences; Substitution, Master Method”.
Which assumption must I keep in mind?+
The formula applies only when quantities are defined as in the source and background. Check boundary cases, measurement conditions and whether an approximation rather than equality is intended. Substitution can be algebraically correct yet technically wrong when assumptions fail or the population or system boundary changes. Validity limit: f(n)∈O(g(n)) means there are constants c>0 and n0 such that |f(n)|≤c|g(n)| for every n≥n0. Constants and lower-order terms are abstracted away, but the cost model still matters: define whether f Source: MIT OpenCourseWare, 6.046J Introduction to Algorithms, Lecture 2: “Asymptotic Notation; Recurrences; Substitution, Master Method”.
Which units and quantities are involved?+
The stated units are: n is input size; f(n) and g(n) use the same cost units; c>0 and n0 are constants. Convert values to a consistent unit system before substitution; counts, percentages and dimensionless ratios are not interchangeable. The variable list states the role of each symbol. Dimensional analysis catches many errors but does not replace checking the formula's assumptions. Validity limit: f(n)∈O(g(n)) means there are constants c>0 and n0 such that |f(n)|≤c|g(n)| for every n≥n0. Constants and lower-order terms are abstracted away, but the cost model still matters: define whether f Source: MIT OpenCourseWare, 6.046J Introduction to Algorithms, Lecture 2: “Asymptotic Notation; Recurrences; Substitution, Master Method”.
When is comparison with laufzeitrekurrenz and shannon-entropie useful?+
Comparison helps when both quantities address the same question but emphasize different properties. Report the definition, input data, threshold or averaging with the value. The source MIT OpenCourseWare, 6.046J Introduction to Algorithms, Lecture 2: “Asymptotic Notation; Recurrences; Substitution, Master Method”. supports the definition used here; other conventions can differ. Choose the measure to match the learning or analysis goal. Validity limit: f(n)∈O(g(n)) means there are constants c>0 and n0 such that |f(n)|≤c|g(n)| for every n≥n0. Constants and lower-order terms are abstracted away, but the cost model still matters: define whether f Source: MIT OpenCourseWare, 6.046J Introduction to Algorithms, Lecture 2: “Asymptotic Notation; Recurrences; Substitution, Master Method”.
Quanta exam set
Curated exam set for "Big-O notation (asymptotic upper bound)":
Question (front)
Which formula describes Big-O notation (asymptotic upper bound)?
Answer in your set
Question (front)
How do you rearrange Big-O notation (asymptotic upper bound) for Defining relation?
Answer in your set
Question (front)
Which common mistake happens with Big-O notation (asymptotic upper bound)?
Answer in your set
+ 7 more cards: units, variables, derivation, example, exam task
The formula set contains 10 cards. After importing, review them and start practicing; your ratings determine later review intervals.
Subject references and further reading
This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.
Related formulas
More formulas: Algorithms, number representation and cryptography
Retain Big-O notation (asymptotic upper bound) for exams
Create a curated FSRS exam set for f(n) ∈ O(g(n)): formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.
Curated formula set · LaTeX · FSRS spaced repetition · import from Essential