Asymptotic upper bounds and big O
Big O bounds eventual growth up to a fixed constant factor.
Key knowledge
For nonnegative cost functions, T(n)=O(g(n)) means there are constants c>0 and n₀ such that T(n)≤cg(n) for every n≥n₀. A time or space complexity bound must specify the computation model, input-size measure and case being analysed.
Values and equations
T(n)=O(g(n)) ⇔ ∃c>0, n₀: 0≤T(n)≤cg(n) for all n≥n₀
- T(n)
- Nonnegative resource cost at input size n
- g(n)
- Nonnegative comparison function
- c
- Fixed positive multiplier
- n₀
- Fixed threshold input size
- n
- Input size in the declared representation
Conditions and scope
- Constants c and n₀ are fixed independently of n.
- An upper bound need not be tight and does not specify wall-clock duration.
- Worst-case, average-case and amortised costs are different quantities.
Sources · 5
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
National Institute of Standards and Technology (NIST)4 sources
- Dictionary of Algorithms and Data Structures: Big-O notationPaul E. Black / US National Institute of Standards and TechnologyReference guide
- Dictionary of Algorithms and Data Structures: Worst caseUS National Institute of Standards and TechnologyReference guide
- Dictionary of Algorithms and Data Structures: Average caseUS National Institute of Standards and TechnologyReference guide
- Dictionary of Algorithms and Data Structures: Amortized costUS National Institute of Standards and TechnologyReference guide
- Data Structures and Algorithms · IntroductionUniversity of HelsinkiTeaching resource
Evidence and review
Nonnegative-cost big-O definition and resource-growth interpretation.
2026-10-10 · Checked constants and asymptotic scope; no performance claim about a particular implementation.
Foundational review
2026-10-10 · Fresh primary-source inspection of the complete compact record, including every statement, equation, quantity and material condition, followed by independent AI editorial review. This check does not certify all linked lessons or every passage of every cited publication.
Sources from other places
Agreement within this scope
Big-O uses fixed constants and an eventual upper bound on operations as input length grows.
An upper bound is not a single-machine wall-clock measurement.
University of Helsinki, Department of Computer Science
- Data Structures and Algorithms · Introduction FinlandEnglish
Efficiency of algorithms; Analysis of algorithms
- Data Structures and Algorithms · Introduction
Entry details
Permanent link to this entry ↗- Record identity
- info-asymptotic-complexity
- Revision
- core.1
- Structured reference record
- Essential core · first collection