Theory → Algorithmic Analysis
Time Complexity
A measure of how an algorithm’s running time grows with input size.
Motivation
Time complexity solves the problem of comparing algorithms without depending on one machine, one language, or one input sample.
Where it fits
It belongs to algorithmic analysis. It explains why an algorithm that works on 100 items may fail on 100 million.
Subconcepts
Polynomial time
Growth such as O(n), O(n log n), or O(n²). These are often considered tractable, depending on constants and input size.
Exponential time
Growth such as O(2ⁿ). These algorithms can become infeasible very quickly.
Mental model
Time complexity is about how work grows as input grows.
Common mistakes
- Treating Big O as exact runtime.
- Ignoring constants for small inputs.
- Comparing algorithms without considering expected input size.