Time & Space Complexity
Learn how to analyze algorithms and understand Big O notation to write more efficient code.
What is Big O Notation?
Big O notation describes how an algorithm's runtime or space requirements grow as the input size increases. It provides an upper bound on the growth rate.
Key Principles
- Worst Case: Big O typically describes worst-case performance
- Drop Constants: O(2n) simplifies to O(n)
- Drop Lower Terms: O(n² + n) simplifies to O(n²)
Common Complexities
O(1)
Constant
Same time regardless of input size
Array access, hash lookup
O(log n)
Logarithmic
Halves problem size each step
Binary search
O(n)
Linear
Proportional to input size
Loop through array
O(n log n)
Linearithmic
Efficient sorting complexity
Merge sort, quick sort
O(n²)
Quadratic
Nested iterations
Bubble sort, nested loops
O(2�?
Exponential
Doubles with each addition
Naive recursionSpace Complexity
Space complexity measures how much additional memory an algorithm needs relative to input size.
Space Complexity Examples
// O(1) Space - constant extra space
function sum(arr) {
let total = 0; // One variable
for (let num of arr) {
total += num;
}
return total;
}
// O(n) Space - proportional to input
function double(arr) {
const result = []; // New array of size n
for (let num of arr) {
result.push(num * 2);
}
return result;
}Practical Examples
| Operation | Time | Space |
|---|---|---|
| Array access by index | O(1) | O(1) |
| Array search (unsorted) | O(n) | O(1) |
| Binary search | O(log n) | O(1) |
| Quick sort | O(n log n) | O(log n) |
| Merge sort | O(n log n) | O(n) |