A characterization of the growth rate of an algorithm's running time as a function of input size, typically expressed asymptotically (e.g., Big O) to compare scalability.

Principle

Resource usage is abstracted to functions of input size so that dominant terms determine asymptotic behavior, enabling comparisons independent of machine-specific constants.

Demonstration

Quicksort has average-case time complexity O(n log n), while insertion sort has worst-case O(n^2); for large n, Quicksort scales better despite constant factors.

Misapplication

Using Big O as an exact runtime, ignoring average vs worst-case distinctions, or selecting algorithms solely by asymptotic class when constants and input distributions matter.

Consequence

Proper use informs algorithm selection, predicts performance trends for large inputs, and drives complexity-theoretic tradeoffs in design and optimization.

Reversal

Focusing exclusively on constant factors and microbenchmarks without regard to asymptotic growth, which can mask poor scaling for large inputs.

Boundary

Concerns time as an abstract resource measured against input size; excludes implementation-dependent constant-time details, hardware-specific optimizations, and non-time resources like memory or energy (unless explicitly included).

Semantic Tension

Tends to be conflated with empirical runtime or 'efficiency'; time complexity is an asymptotic, model-based abstraction rather than an exact performance metric.

Synthesis

Algorithmic time complexity is the asymptotic description of how an algorithm's running time grows with input size, used to evaluate scalability and guide algorithm choice under idealized cost models.