Time Complexity
Time complexity measures how the number of basic operations an algorithm performs grows with input size.
Counting steps, not seconds
Time complexity counts elementary operations, such as comparisons or arithmetic steps, as a function of input size n. It deliberately avoids wall-clock seconds because those depend on hardware. The result is a machine-independent measure expressed in big-O terms.
Input size is the variable
Everything is stated relative to n, the size of the input in some natural unit: the number of array elements, the count of graph vertices, or the number of bits in an integer. Choosing the right size measure matters; for number-theoretic problems the size is the bit length, not the numeric value.
Common classes
- Constant O(1): array index lookup
- Logarithmic O(log n): binary search
- Linear O(n): scanning a list
- Linearithmic O(n log n): efficient sorting
- Quadratic O(n^2): naive all-pairs comparison
- Exponential O(2^n): brute-force subset search
Worst versus average
Worst-case time complexity bounds the hardest input and gives a guarantee. Average-case assumes a distribution of inputs and can be more optimistic. Quicksort, for example, is O(n^2) worst case but O(n log n) on average, which is why it performs well in practice despite the bad worst case.
Polynomial versus exponential
The great divide in time complexity is polynomial versus exponential. Polynomial-time algorithms (n, n^2, n^3) are considered tractable; exponential ones become unusable as n grows because doubling the input can square or double the work. This divide underlies the classes P and NP.
A practical note
Lower time complexity usually wins at scale, but not always at the sizes you run. Always pair the asymptotic class with the input sizes you expect and, where it matters, with real measurement. Time complexity tells you the shape of the curve; measurement tells you where you sit on it.