Concept Architecture
Concept
Theoretically, Computational Complexity is the mathematical study of the computational resources required by an algorithm as a function of input size. It is founded on computational complexity theory and algorithm analysis, providing a framework for classifying algorithms according to their asymptotic requirements for time and memory. The concept exists to enable objective comparison of algorithms independently of specific hardware or programming languages and to identify computationally efficient methods for solving mathematical and optimisation problems.
Mathematically, computational complexity is represented using asymptotic notation, principally Big O, Big � and Big � notation, which describe upper, lower and tight bounds on algorithm growth as input size increases. Complexity is expressed as a function of input size n and characterises the rate at which computational time or memory consumption increases. The mathematical framework underpins the analysis of optimisation algorithms, numerical methods and machine learning procedures commonly applied in health economics.
In practice, computational complexity is estimated through theoretical algorithm analysis and empirical benchmarking. It is routinely reported when selecting optimisation methods, simulation algorithms and statistical estimation procedures. In health economics, computational complexity influences the feasibility of large-scale microsimulation, Markov modelling, probabilistic sensitivity analysis, Bayesian inference and machine learning applications by determining computational time and resource requirements.
Purpose
Used to quantify the computational resources required by algorithms, supporting the selection, comparison and implementation of efficient computational methods in health economic modelling and analysis.
Mathematical Formulae
Primary Formula
T(n) ? O(f(n))
Supporting Formulae
Upper bound:
T(n) ? O(f(n))
Lower bound:
T(n) ? �(f(n))
Tight bound:
T(n) ? �(f(n))
Common complexity classes:
O(1), O(log n), O(n), O(n log n), O(n�), O(2�)
Related Mathematical Methods
- Big O Notation
- Big � Notation
- Big � Notation
- Asymptotic Analysis
- Algorithm Analysis
- Numerical Analysis
Example
Two algorithms are available for analysing a cohort of 10,000 patients.
Algorithm A has time complexity O(n).
Algorithm B has time complexity O(n�).
For n = 10,000:
Algorithm A performs approximately proportional to 10,000 operations.
Algorithm B performs approximately proportional to 100,000,000 operations.
Although both algorithms produce identical analytical results, Algorithm A is substantially more computationally efficient and is therefore preferred for large-scale health economic simulations.
Excel Implementation
| Function | Example Formula | Health Economics Application |
|---|---|---|
| POWER | =POWER(n,2) | Estimates quadratic computational growth. |
| LN | =LN(n) | Calculates logarithmic terms for complexity comparisons. |
| ROWS | =ROWS(DataRange) | Determines input size for computational analyses. |
| PRODUCT | =n*LN(n) | Estimates n log n growth for algorithm comparisons. |
| IF | =IF(Time1<Time2,"Algorithm A","Algorithm B") | Compares empirical execution times of alternative algorithms. |
VBA (Optional)
VBA can automate benchmarking of alternative algorithms by recording execution times across increasing dataset sizes and summarising empirical computational complexity.
Sources
- Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms.
- Sipser M. Introduction to the Theory of Computation.
- Knuth DE. The Art of Computer Programming.
- 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 (2)
Library
Publications
2
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 →
Frequently Asked Questions (6)
What is computational complexity?
A measure of the computational resources required by an algorithm as the size of the input increases.
Source: Black PE. Complexity. In: Dictionary of Algorithms and Data Structures. NIST; 2004.
What does computational complexity measure?
Computational complexity measures the computational resources required by an algorithm as the size of the input increases, so it describes how demand for those resources scales rather than a fixed cost. By relating resource use to input size, computational complexity captures how an algorithm behaves as problems grow larger. This makes computational complexity a way to compare algorithms by how well they cope with increasing amounts of data By describing how demand for resources rises with input size rather than any single measurement, computational complexity gives a general basis for judging which algorithm will remain practical as problems grow.
Source: Black PE. Complexity. In: Dictionary of Algorithms and Data Structures. NIST; 2004.
Why is computational complexity expressed in terms of input size?
Computational complexity is expressed in terms of input size because it measures how the resources required by an algorithm change as that size increases. A single figure for one input would say little about how the algorithm copes with larger problems, so computational complexity describes the trend as input grows. Relating resource use to input size is what lets computational complexity reveal how an algorithm scales By describing how demand for resources rises with input size rather than any single measurement, computational complexity gives a general basis for judging which algorithm will remain practical as problems grow.
Source: Black PE. Complexity. In: Dictionary of Algorithms and Data Structures. NIST; 2004.
What resources does computational complexity concern?
Computational complexity concerns the computational resources required by an algorithm, most often the running time or the memory it consumes, considered as the size of the input increases. Focusing on how these resources grow rather than on any single measurement lets computational complexity describe an algorithm's demands in a general way. This concern with resource growth is central to how computational complexity characterises an algorithm By describing how demand for resources rises with input size rather than any single measurement, computational complexity gives a general basis for judging which algorithm will remain practical as problems grow.
Source: Black PE. Complexity. In: Dictionary of Algorithms and Data Structures. NIST; 2004.
Why does computational complexity matter when choosing an algorithm?
Computational complexity matters when choosing an algorithm because it measures how the resources required grow as the size of the input increases, and an algorithm that scales poorly may become impractical on large inputs. Two algorithms that solve the same problem can differ sharply in complexity, so comparing their computational complexity helps predict which remains usable as data grows. This makes computational complexity a key consideration in algorithm selection By describing how demand for resources rises with input size rather than any single measurement, computational complexity gives a general basis for judging which algorithm will remain practical as problems grow.
Source: Black PE. Complexity. In: Dictionary of Algorithms and Data Structures. NIST; 2004.
How does computational complexity relate to time complexity?
Computational complexity is a measure of the computational resources required by an algorithm as input size increases, while time complexity is a measure specifically of how the execution time of an algorithm grows with input size. Time complexity is therefore one component of computational complexity, alongside memory and other resources. The two are connected in that time complexity narrows the general idea of computational complexity to the resource of running time By describing how demand for resources rises with input size rather than any single measurement, computational complexity gives a general basis for judging which algorithm will remain practical as problems grow.
Source: Black PE. Complexity. In: Dictionary of Algorithms and Data Structures. NIST; 2004.
Trust Record
Verified by Dr Darrin Baines
British health economist
Professional identity: darrinbaines.org
Verification date: 20 Mar 2026
Content version: 1.0.0
Canonical Identity
- Term code
- CS-SC-PF-006
Stable URI · Machine-readable · Resolvable · CC BY 4.0