Complexity analysis is the process of evaluating how efficiently an algorithm uses computational resources as its input size grows. The two primary resources considered are time and space.
Instead of measuring the exact execution time or memory consumption on one computer, complexity analysis studies how resource requirements scale with input size. This makes it possible to compare algorithms independently of hardware and implementation details.
Complexity analysis is fundamental to data structures and algorithms because choosing an appropriate data structure or algorithm can significantly affect how an application behaves when the amount of data increases.
What Is Complexity Analysis?
Suppose two algorithms both search for a value in an array. One checks elements one by one, while another uses binary search on sorted data. Both may produce the same result, but their resource requirements can grow differently.
function linearSearch(numbers, target) {
for (const number of numbers) {
if (number === target) {
return true;
}
}
return false;
}A linear search may inspect every element, resulting in O(n) worst-case time. Complexity analysis allows this behavior to be described without depending on the exact size of the array or the speed of the computer running the program.
The Two Main Types of Complexity
| Type | What It Measures |
|---|---|
| Time Complexity | How computational work grows with input size |
| Space Complexity | How memory requirements grow with input size |
An algorithm can have efficient time complexity but require significant additional memory, or use very little additional memory while requiring more computational work. Complexity analysis helps make these trade-offs visible.
Input Size
Complexity is normally expressed in terms of an input-size variable such as
n.
The meaning of n depends on the problem. It can represent the number of array elements, characters in a string, records in a collection, or nodes in a tree.
const numbers = [10, 20, 30, 40, 50];
// n = 5
For more complex problems, multiple variables may be necessary. Graph algorithms,
for example, commonly use V for vertices and
E for edges.
Asymptotic Analysis
Complexity analysis commonly uses asymptotic analysis to describe how an algorithm behaves as the input size becomes large.
Asymptotic analysis focuses on growth rather than exact operation counts. This allows algorithms to be compared using mathematical expressions such as O(n), O(log n), and O(n²).
Big O Notation
Big O notation is commonly used to describe an asymptotic upper bound on an algorithm's growth. In everyday algorithm discussions, it is frequently used to communicate worst-case time or space complexity.
function printAll(numbers) {
for (const number of numbers) {
console.log(number);
}
}The loop processes each of the n elements, so the running time grows linearly: O(n).
Common Complexity Classes
Different algorithms can have very different growth rates. Some of the most common complexity classes are:
| Complexity | Name | Example |
|---|---|---|
| O(1) | Constant | Array index access |
| O(log n) | Logarithmic | Binary search |
| O(n) | Linear | Linear search |
| O(n log n) | Linearithmic | Merge sort |
| O(n²) | Quadratic | Simple nested loops |
| O(2ⁿ) | Exponential | Some branching recursive algorithms |
| O(n!) | Factorial | Generating permutations |
Analyzing Constant-Time Operations
A constant-time operation does not grow with the input size. Accessing an element at a known array index is a common example.
function getElement(numbers, index) {
return numbers[index];
}The operation requires a fixed amount of work regardless of how many other elements exist in the array, so it is O(1).
Analyzing Linear Operations
When an operation is performed once for every input element, the complexity is generally O(n).
function calculateSum(numbers) {
let sum = 0;
for (const number of numbers) {
sum += number;
}
return sum;
}The loop visits n elements, giving O(n) time complexity.
Analyzing Nested Loops
When two independent loops are nested and each can run n times, their combined work is approximately n × n.
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]);
}
}
}The resulting time complexity is O(n²).
Nested Loops Are Not Always O(n²)
The presence of a loop inside another loop does not automatically mean O(n²). The total number of executions must be analyzed.
let j = 0;
for (let i = 0; i < n; i++) {
while (j < n) {
j++;
}
}The outer loop runs n times, but j increases from 0 to n only once overall. The total work is therefore O(n), rather than O(n²).
Sequential Operations
When operations execute one after another, their complexities are added.
for (let i = 0; i < n; i++) {
console.log(i);
}
for (let j = 0; j < n; j++) {
console.log(j);
}The total complexity is O(n + n), which simplifies to O(n) after removing the constant factor.
Dominant Terms
When several terms appear in a complexity expression, the term that grows fastest generally determines the final asymptotic complexity.
T(n) = n² + n + 100
// Dominant term: n²
// Complexity: O(n²)The lower-order terms become less significant relative to n² as the input grows.
Ignoring Constant Factors
Asymptotic analysis normally ignores constant multipliers.
T(n) = 5n + 20
// Simplified complexity: O(n)Likewise, 3n² + 7n + 10 is simplified to O(n²). This allows algorithms to be compared according to their growth patterns rather than exact operation counts.
Analyzing Logarithmic Complexity
An algorithm often has O(log n) complexity when each iteration reduces the remaining problem by a constant factor.
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 removes roughly half of the remaining search space, so the worst-case time complexity is O(log n).
Analyzing Recursion
Recursive algorithms require analysis of both the number of recursive calls and the amount of work performed by each call.
function countdown(n) {
if (n <= 0) {
return;
}
console.log(n);
countdown(n - 1);
}There is one recursive call for each decrement of n, so the time complexity is O(n). Because the calls remain active on the call stack, the auxiliary space is also O(n).
Analyzing Recursive Branching
When a recursive function makes multiple recursive calls, the number of calls can grow much faster.
function countWays(n) {
if (n <= 1) {
return 1;
}
return countWays(n - 1) + countWays(n - 2);
}This straightforward recursive Fibonacci-style implementation repeatedly solves the same subproblems. Its time complexity grows exponentially in its naive form, while techniques such as memoization can avoid much of the repeated work.
Best-Case, Average-Case, and Worst-Case Analysis
The same algorithm can perform differently depending on the input. Complexity analysis can therefore consider three common cases.
- Best case: The input causes the algorithm to perform the least amount of work.
- Average case: The expected behavior under a specified or assumed input distribution.
- Worst case: The input causes the algorithm to perform the greatest amount of work.
function linearSearch(numbers, target) {
for (let i = 0; i < numbers.length; i++) {
if (numbers[i] === target) {
return i;
}
}
return -1;
}For linear search, finding the target at the first position takes O(1), while finding it at the last position or not finding it at all requires O(n) comparisons.
Space Complexity Analysis
Complexity analysis also considers memory. In particular, developers often analyze auxiliary space, which is the additional memory required beyond the input.
function createCopy(numbers) {
const copy = [];
for (const number of numbers) {
copy.push(number);
}
return copy;
}The function creates a new collection that can contain n elements. Therefore, its auxiliary space complexity is O(n).
In-Place Algorithms
An algorithm is commonly described as in-place when it performs its primary work by modifying existing data while using only a small amount of additional memory.
function reverseArray(numbers) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
[numbers[left], numbers[right]] =
[numbers[right], numbers[left]];
left++;
right--;
}
}Only a fixed number of variables are used, so the auxiliary space is O(1).
Time-Space Trade-Off
An algorithm can sometimes use additional memory to reduce the amount of computation required. This is known as a time-space trade-off.
function hasDuplicate(numbers) {
const seen = new Set();
for (const number of numbers) {
if (seen.has(number)) {
return true;
}
seen.add(number);
}
return false;
}The set can store up to n values, requiring O(n) additional space in the worst case. In exchange, membership checks are typically O(1) on average, allowing the duplicate detection algorithm to run in O(n) expected time rather than repeatedly comparing every pair of elements.
Complexity of Common Data Structures
Understanding complexity is closely connected to understanding the operations supported by data structures.
| Data Structure | Operation | Typical Complexity |
|---|---|---|
| Array | Index access | O(1) |
| Array | Search | O(n) |
| Linked List | Search | O(n) |
| Stack | Push / Pop | O(1) |
| Queue | Enqueue / Dequeue | O(1)* |
| Hash Table | Lookup | O(1) average |
| Balanced BST | Search | O(log n) |
| Heap | Insertion | O(log n) |
* Assuming an appropriate queue implementation with efficient front and rear tracking. Actual complexity can vary depending on the implementation and operation being analyzed.
Graph Complexity
Graph algorithms often require more than one input-size variable. A graph is commonly described using the number of vertices, V, and the number of edges, E.
For example, breadth-first search and depth-first search using an adjacency-list representation generally have O(V + E) time complexity because vertices and edges are processed.
The graph representation also affects space complexity. An adjacency list typically requires O(V + E) space, while an adjacency matrix requires O(V²) space.
How to Analyze an Algorithm
- Identify the input size and define variables such as n, V, or E.
- Identify the operations whose execution count changes with the input.
- Analyze loops and determine how many times they execute.
- Check whether loops are sequential, nested, or dependent on changing variables.
- Analyze recursive calls and the depth or branching of recursion.
- Identify additional collections and memory allocations.
- Combine the complexity of independent sections.
- Remove constant factors and lower-order terms.
- Identify the dominant growth term.
- Express the final time and space complexity using asymptotic notation.
Worked Complexity Analysis Example
function process(numbers) {
const result = [];
for (const number of numbers) {
result.push(number * 2);
}
for (let i = 0; i < numbers.length; i++) {
for (let j = 0; j < numbers.length; j++) {
console.log(numbers[i], numbers[j]);
}
}
return result;
}The first loop processes n elements, giving O(n) time. The nested loops perform approximately n² operations, giving O(n²) time.
Combining them produces O(n + n²). The dominant term is n², so the overall time complexity is O(n²).
The result array can contain n elements, so the auxiliary space complexity is O(n).
Complexity Analysis in Coding Interviews
Complexity analysis is frequently used in technical interviews to evaluate whether a candidate understands the performance characteristics of their solution.
A useful explanation should identify the input size, describe the major operations, state the time complexity, and mention additional space when relevant.
function containsDuplicate(numbers) {
const seen = new Set();
for (const number of numbers) {
if (seen.has(number)) {
return true;
}
seen.add(number);
}
return false;
}A concise analysis would be: the algorithm scans n elements once, and each set lookup is O(1) on average. Therefore, the expected time complexity is O(n), while the set can store n elements, giving O(n) auxiliary space.
Common Complexity Analysis Mistakes
- Confusing Big O with exact execution time.
- Assuming every nested loop automatically produces O(n²).
- Forgetting to analyze recursive calls.
- Ignoring memory allocated by temporary collections.
- Keeping constant factors in the final asymptotic expression.
- Ignoring lower-order terms when simplifying complexity.
- Analyzing only the best case when worst-case behavior matters.
- Using the same input variable for problems that have multiple independent input sizes.
- Ignoring the implementation details of a data structure.
- Reporting only time complexity when additional space is significant.
A Practical Complexity Checklist
When reviewing an algorithm, the following checklist can make complexity analysis more systematic:
- What is the input size?
- How many times does the main operation execute?
- Are there sequential loops?
- Are there nested loops?
- Does a loop reduce or increase the problem size by a factor?
- Does the algorithm use recursion?
- How deep can the recursion become?
- Does the algorithm create additional arrays, maps, sets, or matrices?
- Which complexity term grows the fastest?
- What are the final time and auxiliary-space complexities?
Key Takeaways
- Complexity analysis evaluates how algorithm resource requirements grow with input size.
- Time complexity measures computational work, while space complexity measures memory growth.
- Big O notation is commonly used to communicate asymptotic upper-bound behavior.
- O(1), O(log n), O(n), O(n log n), and O(n²) are common complexity classes.
- Sequential operations are combined by addition, while nested operations require careful execution-count analysis.
- Nested loops do not automatically mean O(n²).
- Constants and lower-order terms are normally removed from asymptotic expressions.
- Recursive algorithms require analysis of both execution and call-stack usage.
- Additional data structures can increase space complexity while improving time complexity.
- For graphs, both vertices and edges may contribute to complexity.
- Good complexity analysis identifies the input size, dominant operations, time complexity, and relevant space usage.