Time Complexity

Concept

Theoretically, Time Complexity is the mathematical analysis of the computational time required by an algorithm as a function of input size. It is one of the fundamental measures of algorithmic efficiency and enables objective comparison of computational methods independently of computer hardware. Time complexity forms a core component of computational complexity theory and underpins the design and evaluation of algorithms used in health economic modelling, optimisation, simulation, and data analysis.

Mathematically, time complexity is expressed using asymptotic notation, most commonly Big O notation, which describes the growth rate of the number of elementary operations performed as the input size increases. Rather than measuring actual execution time, time complexity evaluates how computational effort scales with problem size by considering the dominant term of the algorithm.

In practice, time complexity is used to select efficient algorithms for large healthcare datasets, probabilistic sensitivity analyses, Monte Carlo simulations, pharmacometric models, optimisation methods, and machine learning applications. Understanding computational complexity allows analysts to predict scalability, estimate computational resources, and optimise model performance.

Purpose

Time complexity quantifies the computational effort required by an algorithm as input size increases, allowing comparison of alternative algorithms and supporting efficient implementation of computational methods in health economics and related disciplines.

Mathematical Formulae

Primary Formula

T(n) = O(f(n))

Where:

• T(n) = time complexity
• n = input size
• f(n) = asymptotic growth function

Supporting Formulae

Total Running Time

T(n) = Number of Operations ? Cost per Operation

Common Complexity Classes

O(1) Constant time

O(log n) Logarithmic time

O(n) Linear time

O(n log n) Linearithmic time

O(n�) Quadratic time

O(n?) Cubic time

O(2�) Exponential time

O(n!) Factorial time

Related Mathematical Methods

• Computational Complexity Theory
• Big O Notation
• Big Theta Notation
• Big Omega Notation
• Algorithm Analysis
• Recurrence Relations
• Divide and Conquer Analysis
• Dynamic Programming
• Numerical Algorithms
• Computational Optimisation

Example

A health economic simulation analyses outcomes for 100,000 patients.

Algorithm A processes each patient once.

T(n) = O(n)

Algorithm B compares every patient with every other patient.

T(n) = O(n�)

As the dataset grows, Algorithm A scales efficiently, whereas Algorithm B becomes computationally expensive. Selecting the lower-complexity algorithm substantially reduces execution time for large healthcare models.

Excel Implementation

Input Size

=A2

Linear Operations

=A2

Logarithmic Operations

=LOG(A2,2)

Linearithmic Operations

=A2*LOG(A2,2)

Quadratic Operations

=A2^2

Cubic Operations

=A2^3

Complexity Classification

=CHOOSE(B2,"O(1)","O(LOG N)","O(N)","O(N LOG N)","O(N^2)","O(N^3)")

VBA (Optional)

Time complexity can be investigated in VBA by:

• Counting algorithm iterations
• Benchmarking alternative algorithms
• Comparing recursive and iterative methods
• Profiling execution time for increasing input sizes
• Optimising simulation routines
• Evaluating scalability of health economic models

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.

Aho AV, Hopcroft JE, Ullman JD. The Design and Analysis of Computer Algorithms.

Briggs AH, Claxton K, Sculpher MJ. Decision Modelling for Health Economic Evaluation.