Time Complexity
Time complexity is a measure of the amount of time an algorithm takes to complete as a function of the size of its input, typically expressed using Big O notation. It describes how the running time grows relative to the input size, helping developers predict performance and compare algorithms. Understanding time complexity is essential for writing scalable software, especially when dealing with large datasets.
Key Formula
T(n) = O(f(n))
LaTeX: T(n) = O(f(n))
| Symbol | Meaning | Unit |
|---|---|---|
| T(n) | Running time of the algorithm | operations |
| n | Size of the input | elements |
| f(n) | Mathematical function bounding the growth rate | dimensionless |
Worked Example
Problem
An algorithm iterates through an array of n=100 elements once, then iterates through it again in a nested loop. What is the time complexity?
Solution
Step 1: The first single loop runs n times → O(n). Step 2: The nested loop runs n × n times → O(n²). Step 3: Total time = O(n) + O(n²). Step 4: Drop the lower-order term: the dominant term is O(n²).
Answer
O(n²) — quadratic time complexity.
Common Time Complexity Classes
| Notation | Name | Example Algorithm | n=10 ops | n=100 ops |
|---|---|---|---|---|
| O(1) | Constant | Array index lookup | 1 | 1 |
| O(log n) | Logarithmic | Binary search | 3 | 7 |
| O(n) | Linear | Linear search | 10 | 100 |
| O(n log n) | Linearithmic | Merge sort | 33 | 664 |
| O(n²) | Quadratic | Bubble sort | 100 | 10,000 |
| O(2ⁿ) | Exponential | Recursive Fibonacci | 1,024 | 1.27 × 10³⁰ |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
Big O Notation
Big O notation is a mathematical notation used to describe the upper bound of an algorithm's growth rate in terms of time or space, characterising its worst-case performance as the input size approaches infinity. It abstracts away constant factors and lower-order terms, focusing on the dominant factor that determines scalability. Big O is the industry standard language for comparing algorithm efficiency and is essential for technical interviews and software engineering.
Space Complexity
Space complexity is a measure of the amount of memory an algorithm requires as a function of the size of its input, expressed in Big O notation. It includes both the memory needed to store the input (input space) and any additional auxiliary memory allocated during execution (auxiliary space). Optimising space complexity is critical in memory-constrained environments such as embedded systems or mobile devices.
Algorithm
An algorithm is a finite, ordered sequence of well-defined instructions or rules designed to solve a specific problem or accomplish a task. Algorithms are fundamental to computer science because they provide a systematic approach to computation, independent of any particular programming language or hardware. They are evaluated on correctness, efficiency, and clarity, and form the basis of every software program ever written.
The term "time complexity" emerged from computational complexity theory, a branch of theoretical computer science formalized in the 1960s. Key contributions came from Juris Hartmanis and Richard Stearns, who introduced the notion of computational complexity in their 1965 paper.