Time complexity is a measure of how the number of basic operations an algorithm performs grows with the size of its input, expressed as a function of the input size n. In the study of algorithms, time complexity is the standard way to compare approaches independently of hardware, programming language or compiler, usually written in asymptotic notation such as O(n) or O(n log n).
Time complexity does not predict an exact running time in seconds. It describes the growth rate, which decides whether an algorithm that works on a thousand items will still work on a billion.
How time complexity is determined
Time complexity is determined by counting the basic steps an algorithm executes, such as comparisons, assignments or arithmetic operations, as a function of the input size. Each step is assumed to take constant time, a simplification known as the RAM model of computation.
The analysis then keeps only the dominant term and drops constant factors. An algorithm that performs 3n² + 5n + 20 steps has time complexity O(n²), because for large n the squared term overwhelms the rest. Loops are the main source of growth: a single loop over n items usually contributes O(n), two nested loops O(n²), and a loop that halves the problem each time O(log n).
Recursive algorithms are analyzed with recurrence relations. Merge sort, for example, splits the input in half and merges in linear time, giving T(n) = 2T(n/2) + O(n), which solves to O(n log n); the master theorem solves many recurrences of this divide-and-conquer form directly.
Common complexity classes
Most practical algorithms fall into a small set of complexity classes, and the gap between them becomes enormous as n grows. The table shows approximate step counts for an input of one million items.
| Class | Name | Approximate steps for n = 1,000,000 | Example |
|---|---|---|---|
| O(1) | Constant | 1 | Array access by index |
| O(log n) | Logarithmic | About 20 | Binary search |
| O(n) | Linear | 1,000,000 | Scanning a list once |
| O(n log n) | Linearithmic | About 20,000,000 | Merge sort, heapsort |
| O(n²) | Quadratic | 10¹² | Comparing every pair |
| O(2ⁿ) | Exponential | Astronomically large | Brute-force subset search |
At roughly 10⁸ to 10⁹ simple operations per second on current hardware, an O(n log n) algorithm on a million items finishes in a fraction of a second, while an O(n²) algorithm needs minutes to hours. This difference, not micro-optimization, usually decides whether software scales.
Best, average, worst and amortized cases
The same algorithm can have different time complexities depending on the input, so analysis states which case it describes. Unless stated otherwise, a single complexity figure usually refers to the worst case, because it gives a guarantee.
| Analysis | What it describes | Example |
|---|---|---|
| Worst case | Maximum steps over all inputs of size n | Quicksort with poor pivots: O(n²) |
| Average case | Expected steps over a distribution of inputs | Quicksort with random pivots: O(n log n) |
| Best case | Minimum steps over all inputs | Insertion sort on sorted data: O(n) |
| Amortized | Average cost per operation over a long sequence | Dynamic array append: O(1) |
Amortized analysis differs from average-case analysis because it involves no probability. It guarantees that a sequence of operations costs at most a certain total, even if a single operation, such as resizing an array, is occasionally expensive.
Time complexity compared with related measures
Time complexity is closely tied to Big O notation and to space complexity, yet each answers a different question. Big O is the notation; time complexity is the quantity being described.
| Concept | What it measures | Relation to time complexity |
|---|---|---|
| Big O | Asymptotic upper bound of any function | Most common notation for time complexity |
| Big Theta and Big Omega | Tight bound and lower bound | More precise descriptions of growth |
| Space complexity | Growth of memory use | Often traded against time |
| Wall-clock time | Measured running time in seconds | Depends on hardware and constants |
| Computational complexity class | Difficulty of problems, such as P or NP | Applies to problems, not single algorithms |
A frequent time-memory trade-off appears with hash tables and caching: using O(n) extra memory can reduce a lookup from O(n) to an average of O(1).
Pitfalls in interpreting time complexity
Time complexity is a model, not a measurement, and misreading it leads to poor engineering decisions. Experienced developers combine it with profiling on realistic data.
- Ignoring constant factors: for small n, an O(n²) insertion sort often beats an O(n log n) algorithm, which is why practical sorting routines switch to insertion sort for small subarrays.
- Hidden costs in library calls: a membership test on a list inside a loop turns an apparently linear loop into O(n²).
- Assuming the average case: inputs crafted by an attacker can force hash tables or quicksort into their worst case.
- Forgetting memory hierarchy: cache misses and disk access can dominate real performance more than step counts.
- Confusing input size: for numeric algorithms, n may be the number of digits, not the value itself.
A non-technical view
Time complexity tells you how much more work a method needs when the job gets bigger. It does not say how many seconds something takes. It says how fast the effort grows.
Imagine finding a name in a phone book. Reading every page grows with the size of the book. Opening it in the middle and halving the search each time grows very slowly. With a huge book, the smarter method wins by a wide margin, even on a slower reader.
A concrete example
A developer writes a tool that finds duplicate customer records by comparing every record with every other one. With 5,000 records, it finishes in under a second. After a merger, the database grows to 2 million records, and the same job runs for many hours without finishing.
The comparison loop is O(n²), so a 400-fold increase in data means roughly a 160,000-fold increase in work. The developer replaces it with an approach that computes a normalized key for each record and groups records in a hash table, which runs in about O(n) on average.
The new version processes all 2 million records in under a minute on the same server. No faster hardware was needed; the improvement came entirely from changing the growth rate of the algorithm.