Concept Architecture
Concept
Theoretically, Big O Notation is a mathematical notation used to describe the asymptotic upper bound on the growth rate of an algorithm's computational resource requirements as input size increases. It is founded on asymptotic analysis and computational complexity theory and provides a machine-independent framework for comparing algorithmic efficiency. The concept exists to characterise the scalability of algorithms while ignoring constant factors and lower-order terms that become negligible for sufficiently large inputs.
Mathematically, Big O notation expresses an upper bound on the growth of a function representing execution time or memory consumption. If an algorithm requires T(n) operations for an input of size n, then T(n) belongs to O(f(n)) when there exist positive constants c and n? such that T(n) does not exceed c ? f(n) for all n � n?. Common complexity classes include constant, logarithmic, linear, linearithmic, quadratic and exponential growth.
In practice, Big O notation is determined through theoretical analysis of algorithms or empirical examination of their dominant operations. It is widely used to evaluate optimisation algorithms, numerical methods, simulation models and machine learning procedures. In health economics, Big O notation assists in selecting computational methods for microsimulation, probabilistic sensitivity analysis, Bayesian estimation and large-scale decision modelling where computational efficiency is critical.
Purpose
Used to classify the asymptotic computational efficiency of algorithms, supporting comparison, selection and implementation of computational methods in health economic modelling and analysis.
Mathematical Formulae
Primary Formula
T(n) ? O(f(n))
Supporting Formulae
Formal definition:
T(n) ? O(f(n)) if there exist constants c > 0 and n? � 0 such that
T(n) � c ? f(n) for all n � n?
Common complexity classes:
O(1)
O(log n)
O(n)
O(n log n)
O(n�)
O(2�)
Related Mathematical Methods
- Computational Complexity
- Asymptotic Analysis
- Big � Notation
- Big � Notation
- Algorithm Analysis
- Complexity Theory
Example
Two microsimulation algorithms are available for analysing a cohort of 50,000 patients.
Algorithm A has complexity O(n).
Algorithm B has complexity O(n�).
As the cohort size increases, Algorithm A scales approximately in proportion to the number of patients, whereas Algorithm B scales in proportion to the square of the number of patients. For large health economic simulations, Algorithm A is therefore expected to require substantially less computational time.
Excel Implementation
| Function | Example Formula | Health Economics Application |
|---|---|---|
| ROWS | =ROWS(DataRange) | Determines input size (n) for complexity analysis. |
| POWER | =POWER(n,2) | Estimates quadratic growth for comparison purposes. |
| LN | =LN(n) | Calculates logarithmic growth components. |
| PRODUCT | =n*LN(n) | Estimates n log n growth when comparing algorithms. |
| IF | =IF(TimeA<TimeB,"Prefer Algorithm A","Prefer Algorithm B") | Compares empirical execution times of alternative computational methods. |
VBA (Optional)
VBA can automate benchmarking of alternative algorithms across increasing dataset sizes and summarise empirical execution times against theoretical Big O complexity classes.
Sources
- Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms.
- Knuth DE. The Art of Computer Programming.
- Sipser M. Introduction to the Theory of Computation.
- Nocedal J, Wright SJ. Numerical Optimization.
- Briggs A, Claxton K, Sculpher M. Decision Modelling for Health Economic Evaluation.
- Drummond MF, Sculpher MJ, Claxton K, Stoddart GL, Torrance GW. Methods for the Economic Evaluation of Health Care Programmes.
Related Concepts (3)
Library
Publications
4
Computer Science Distilled — Wladston Ferreira Filho, 1st Edition ed., 2017 (Code Energy)
A compact overview of foundational computer science, connecting algorithms, data structures, complexity, recursion, graphs and core computational ideas.
BookView source →Algorithms Illuminated, Part 1: The Basics — Tim Roughgarden, 1st Edition ed., 2017 (Soundlikeyourself Publishing)
An accessible introduction to algorithm analysis, asymptotic notation, divide-and-conquer design, recurrences and comparison-based sorting.
BookView source →Grokking Algorithms — Aditya Y. Bhargava, 1st Edition ed., 2016 (Manning Publications)
An illustrated introduction to practical algorithms, including binary search, sorting, recursion, hash tables, graph search and dynamic programming.
BookView source →A Common-Sense Guide to Data Structures and Algorithms — Jay Wengrow, 2nd Edition ed., 2020 (The Pragmatic Bookshelf)
A practical guide to data structures and algorithm efficiency, covering arrays, hashes, stacks, queues, trees, graphs, heaps, recursion and dynamic programming.
BookView source →
Frequently Asked Questions (6)
What is Big O notation?
An asymptotic notation that expresses an upper bound on how an algorithm’s resource use grows as input size increases, disregarding constant factors and lower-order terms.
Source: Black, P. E. (2019). “Big-O notation.” NIST Dictionary of Algorithms and Data Structures.
What does Big O notation describe?
Big O notation describes an upper bound on how an algorithm's resource use grows as input size increases, so it characterises the worst-case growth rate rather than an exact count. As an asymptotic notation, Big O notation captures the behaviour that dominates when inputs become large, giving a compact way to state how demand for time or memory scales. This lets an algorithm's scalability be summarised by a single growth term By capturing only the dominant growth term, the notation gives a concise, hardware-independent way to compare how different algorithms are expected to scale as their inputs grow large.
Source: Black, P. E. (2019). “Big-O notation.” NIST Dictionary of Algorithms and Data Structures.
Why does Big O notation disregard constant factors and lower-order terms?
Big O notation disregards constant factors and lower-order terms because it is an asymptotic notation concerned with how resource use grows as input size increases rather than with exact quantities. As inputs become large, the dominant term determines growth and the smaller contributions become negligible. By stripping these away, Big O notation focuses attention on the growth behaviour that matters most when comparing how algorithms scale By capturing only the dominant growth term, the notation gives a concise, hardware-independent way to compare how different algorithms are expected to scale as their inputs grow large.
Source: Black, P. E. (2019). “Big-O notation.” NIST Dictionary of Algorithms and Data Structures.
What kind of bound does Big O notation express?
Big O notation expresses an upper bound, meaning it states a ceiling on how an algorithm's resource use grows as input size increases rather than an exact or lower figure. This upper bound holds for sufficiently large inputs, so Big O notation guarantees that growth is no worse than the stated term. Expressing an upper bound is what allows Big O notation to describe worst-case scaling in a single asymptotic expression By capturing only the dominant growth term, the notation gives a concise, hardware-independent way to compare how different algorithms are expected to scale as their inputs grow large.
Source: Black, P. E. (2019). “Big-O notation.” NIST Dictionary of Algorithms and Data Structures.
What resource use can Big O notation characterise?
Big O notation can characterise any resource whose use grows with input size, most commonly running time or memory, since it is an asymptotic notation expressing an upper bound on that growth. By disregarding constant factors and lower-order terms, Big O notation gives a hardware-independent statement of how demand for the resource scales. This generality lets Big O notation describe both time and space requirements in the same asymptotic form By capturing only the dominant growth term, the notation gives a concise, hardware-independent way to compare how different algorithms are expected to scale as their inputs grow large.
Source: Black, P. E. (2019). “Big-O notation.” NIST Dictionary of Algorithms and Data Structures.
How does Big O notation relate to computational complexity?
Big O notation is an asymptotic notation expressing an upper bound on how resource use grows, while computational complexity is a measure of the computational resources required by an algorithm as the size of the input increases. Big O notation is the language commonly used to state computational complexity. The two are connected in that computational complexity is the property being described and Big O notation is the notation used to express its growth By capturing only the dominant growth term, the notation gives a concise, hardware-independent way to compare how different algorithms are expected to scale as their inputs grow large.
Source: Black, P. E. (2019). “Big-O notation.” NIST Dictionary of Algorithms and Data Structures.
Trust Record
Verified by Dr Darrin Baines
British health economist
Professional identity: darrinbaines.org
Verification date: 1 Jul 2025
Content version: 1.0.0
Canonical Identity
- Persistent URI
- https://healtheconomics.wiki/concept/big-o-notation
- Term code
- CS-SC-PF-001
Stable URI · Machine-readable · Resolvable · CC BY 4.0