Time complexity describes how the amount of work performed by an algorithm changes as the size of its input increases. It helps developers understand whether an algorithm will remain practical when working with larger datasets.
Time complexity does not usually mean the exact number of seconds an algorithm takes. Instead, it focuses on the growth of the number of operations relative to the input size.
Understanding time complexity is essential when choosing between data structures, designing algorithms, solving coding problems, and improving application performance.
Why Time Complexity Matters
An algorithm that works well for 100 elements may become impractical when the input contains one million elements. Time complexity provides a way to reason about this behavior before running the algorithm on a large dataset.
- Compare multiple algorithms that solve the same problem.
- Choose appropriate data structures for a task.
- Identify operations that become expensive as input grows.
- Estimate how an algorithm scales with larger datasets.
- Prepare for data structures and algorithm interview questions.
What Is Input Size?
Time complexity is expressed in terms of an input-size variable, commonly represented
by n.
For an array, n usually represents the number of
elements. For a string, it may represent the number of characters. For a graph,
algorithms may use variables such as the number of vertices and edges.
const numbers = [10, 20, 30, 40, 50];
// Input size n = 5The important idea is that the cost of an algorithm is analyzed as the input grows, rather than for one particular input.
Constant Time: O(1)
An operation has constant time complexity when its number of basic operations does not depend on the size of the input.
function getFirstElement(numbers) {
return numbers[0];
}Whether the array contains 10 elements or 10 million elements, accessing a known array position takes a constant number of operations.
Linear Time: O(n)
An algorithm has linear time complexity when the amount of work grows approximately in proportion to the input size.
function printNumbers(numbers) {
for (const number of numbers) {
console.log(number);
}
}
If the input contains n elements, the loop processes
each element once, giving an O(n) time complexity.
Quadratic Time: O(n²)
Quadratic complexity commonly appears when one loop runs inside another loop, with both loops depending on the input size.
function printPairs(numbers) {
for (let i = 0; i < numbers.length; i++) {
for (let j = 0; j < numbers.length; j++) {
console.log(numbers[i], numbers[j]);
}
}
}
For an input of size n, the inner operation can run
approximately n × n times, resulting in O(n²).
Logarithmic Time: O(log n)
An algorithm has logarithmic complexity when it repeatedly reduces the remaining problem by a constant factor. Binary search is a classic example.
function binarySearch(numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left <= right) {
const middle = Math.floor((left + right) / 2);
if (numbers[middle] === target) {
return middle;
}
if (numbers[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return -1;
}Each iteration eliminates approximately half of the remaining search space, resulting in O(log n) time complexity.
Linearithmic Time: O(n log n)
O(n log n) commonly appears in efficient comparison-based sorting algorithms such as merge sort and heap sort.
These algorithms typically divide a problem into smaller parts while processing a substantial portion of the input at each level.
Common Time Complexities
Common time complexity classes can be ordered by how quickly their running cost grows as the input becomes larger.
| Complexity | Common Example | Growth |
|---|---|---|
| O(1) | Array index access | Constant |
| O(log n) | Binary search | Logarithmic |
| O(n) | Linear search | Linear |
| O(n log n) | Merge sort | Linearithmic |
| O(n²) | Nested loops | Quadratic |
| O(2ⁿ) | Some recursive subset algorithms | Exponential |
How to Analyze a Loop
A useful first step when analyzing an algorithm is to determine how many times its main operation can execute.
for (let i = 0; i < n; i++) {
console.log(i);
}
The loop executes approximately n times, so its
complexity is O(n).
Nested Loops
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log(i, j);
}
}The outer loop runs n times and the inner loop also runs n times for each outer iteration. Therefore, the total number of iterations is approximately n².
Sequential Operations
Consider two loops that execute one after another rather than being nested.
for (let i = 0; i < n; i++) {
console.log(i);
}
for (let j = 0; j < n; j++) {
console.log(j);
}The total work is approximately n + n = 2n. When describing asymptotic complexity, constant factors are ignored, so this becomes O(n).
Dropping Constants
Big O focuses on how an algorithm grows rather than exact operation counts. For example, an algorithm that performs 3n operations is still described as O(n).
3n + 10
// Time complexity: O(n)Similarly, 5n² + 2n + 20 is classified as O(n²) because the highest-order growth term dominates as n becomes large.
Best, Average, and Worst Case
An algorithm can behave differently depending on the input. Complexity analysis may therefore discuss the best case, average case, and worst case.
function findNumber(numbers, target) {
for (const number of numbers) {
if (number === target) {
return true;
}
}
return false;
}- Best case: The target is found immediately, requiring O(1) work.
- Worst case: The target is at the end or absent, requiring O(n) work.
- Average case: The number of inspected elements depends on the input distribution and assumptions.
Time Complexity of Common Data Structure Operations
Understanding the complexity of common data structure operations helps when selecting a structure for a particular problem.
| Data Structure | Typical Operation | Average Time |
|---|---|---|
| Array | Index access | O(1) |
| Array | Linear search | O(n) |
| Stack | Push / Pop | O(1) |
| Queue | Enqueue / Dequeue | O(1)* |
| Hash Table | Search | O(1) |
| Binary Search Tree | Search | O(log n)** |
| Heap | Insert | O(log n) |
* Assuming an implementation with appropriate front/rear tracking. ** For a balanced or approximately balanced binary search tree; an unbalanced tree can degrade to O(n).
Time Complexity in Recursion
Recursive algorithms require additional reasoning because one function call can create further calls. Consider a simple recursive function that decreases its input by one.
function countdown(n) {
if (n <= 0) {
return;
}
console.log(n);
countdown(n - 1);
}The function makes approximately n recursive calls, giving O(n) time complexity.
Exponential Complexity
Exponential algorithms can become expensive very quickly because the amount of work grows exponentially with the input size.
function subsets(index, numbers) {
if (index === numbers.length) {
return 1;
}
return (
subsets(index + 1, numbers) +
subsets(index + 1, numbers)
);
}This simplified branching recursion illustrates how repeatedly making multiple recursive calls can lead to exponential growth. The exact complexity depends on the algorithm and recurrence, but this pattern is commonly associated with O(2ⁿ).
Big O, Big Omega, and Big Theta
Asymptotic notation provides different ways to describe algorithm growth.
| Notation | Meaning |
|---|---|
| O(f(n)) | Upper-bound style description of growth |
| Ω(f(n)) | Lower-bound style description of growth |
| Θ(f(n)) | Tight asymptotic bound |
In everyday programming discussions and coding interviews, Big O notation is commonly used to communicate how an algorithm scales, especially when discussing worst-case performance.
How to Find Time Complexity Step by Step
- Identify the input size, usually represented by n.
- Find the operation that contributes most to the running time.
- Determine how many times that operation executes.
- Analyze loops, nested loops, conditionals, and recursive calls.
- Combine sequential operations appropriately.
- Keep the dominant growth term and remove constant factors.
- Express the result using asymptotic notation.
Example: Finding the Complexity of an Algorithm
function findMaximum(numbers) {
let maximum = numbers[0];
for (let i = 1; i < numbers.length; i++) {
if (numbers[i] > maximum) {
maximum = numbers[i];
}
}
return maximum;
}The algorithm first performs a constant-time assignment. It then scans the remaining elements once.
The loop performs approximately n comparisons, so the overall time complexity is O(n).
Common Mistakes When Analyzing Time Complexity
- Confusing actual execution time with asymptotic complexity.
- Assuming every nested-looking block automatically produces O(n²).
- Ignoring the effect of input size on recursive calls.
- Forgetting that operations inside a loop contribute to the loop's complexity.
- Keeping unnecessary constant factors in the final Big O expression.
- Assuming average-case hash table performance is guaranteed for every possible input.
- Ignoring data structure implementation details when analyzing operations.
- Using only the best case when the problem requires understanding worst-case behavior.
Time Complexity vs Space Complexity
Time complexity measures how computational work grows with the input, while space complexity measures how additional memory requirements grow.
function createCopy(numbers) {
const copy = [];
for (const number of numbers) {
copy.push(number);
}
return copy;
}The function processes every element once, so its time complexity is O(n). It also creates a new collection containing n elements, giving O(n) additional space complexity.
Key Takeaways
- Time complexity describes how algorithmic work grows as input size increases.
- O(1) represents constant growth.
- O(log n) commonly appears in algorithms that repeatedly reduce the search space.
- O(n) represents linear growth.
- O(n log n) is common in efficient sorting algorithms.
- O(n²) commonly appears with nested loops over the same input.
- Best, average, and worst cases can have different complexity.
- Constant factors are normally ignored in asymptotic analysis.
- Choosing the right data structure can significantly affect algorithmic complexity.
- Time complexity and space complexity describe different resource requirements.