DSA: Time and Space Complexity Analysis
Learn to measure and compare algorithm efficiency using Big O, Omega, and Theta notation.
Algorithm Complexity
Algorithm complexity measures how the resource usage of an algorithm (time or memory) scales as the input size grows. It lets us compare algorithms independently of hardware or language.
Why Measure Complexity?
Complexity analysis predicts how an algorithm behaves at scale before you run it on real data.
- Time complexity: how the number of operations grows with input size n
- Space complexity: how the memory usage grows with input size n
- We use mathematical notation rather than clock time because hardware varies
- The goal is to classify growth rate, not count exact operations
Big O, Big Omega, and Big Theta
Three notations bound an algorithm from above, below, and both sides. Big O is the most commonly used because it describes the worst-case ceiling.
The Three Asymptotic Notations
Each notation answers a different question about how fast an algorithm can grow.
- Big O (O): upper bound, the algorithm grows no faster than this (worst case ceiling)
- Big Omega (Ω): lower bound, the algorithm takes at least this long (best case floor)
- Big Theta (Θ): tight bound, the algorithm grows exactly at this rate (upper and lower match)
- Example: linear search is O(n), Ω(1), and Θ(n) on average
| Notation | Meaning | Describes |
|---|---|---|
| O(f(n)) | Grows no faster than f(n) | Worst-case ceiling |
| Ω(f(n)) | Grows no slower than f(n) | Best-case floor |
| Θ(f(n)) | Grows exactly like f(n) | Tight / average bound |
Best, Average, and Worst-Case Analysis
The same algorithm can behave very differently depending on the input. Analyzing all three cases gives a complete picture of performance.
Case Analysis
Always consider the worst case when guarantees matter, and the average case for typical workloads.
- Best case: most favorable input, e.g., target is the first element in a search
- Worst case: least favorable input, e.g., target is not in the array
- Average case: expected performance over all possible inputs
- Big O typically describes worst case; Ω describes best case
Linear Search: Three Cases
C++The position of the target determines which case applies.
Common Complexity Classes
Seven complexity classes cover the vast majority of algorithms you will encounter. From fastest to slowest growth:
Complexity Classes from Best to Worst
Aim for O(1) or O(log n) when possible; avoid O(2ⁿ) and O(n!) for anything but tiny inputs.
- O(1): constant, array index access, hash map lookup
- O(log n): logarithmic, binary search, balanced BST operations
- O(n): linear, single loop over all elements
- O(n log n): linearithmic, merge sort, heap sort
- O(n²): quadratic, nested loops, bubble sort
- O(2ⁿ): exponential, naive recursive Fibonacci, subset enumeration
- O(n!): factorial, brute-force permutations
O(1), O(n), and O(n²) Side by Side
C++Each block represents a different complexity class on the same array.
Analyzing Loops and Recursive Functions
Loops contribute multiplicatively to complexity. Nested loops multiply their ranges; sequential loops add. Recursive functions depend on the depth of the call stack and work done per call.
Loop and Recursion Rules
Apply these rules mechanically to derive the Big O of any function.
- A single loop over n elements: O(n)
- Two nested loops each over n: O(n²)
- A loop that halves its range each iteration: O(log n)
- Recursive function with T(n) = T(n-1) + O(1): O(n)
- Recursive function with T(n) = 2T(n/2) + O(n): O(n log n) by Master Theorem
Recursive Complexity
C++factorial is O(n); naive Fibonacci is O(2^n) because it branches twice at every level.
Space Complexity
Space complexity counts the extra memory an algorithm allocates beyond its input. Call stack frames, auxiliary arrays, and containers all count toward space usage.
What Counts as Space
Space complexity focuses on auxiliary memory, not the input itself (unless otherwise stated).
- Variables and pointers: usually O(1)
- An output array of size n: O(n)
- Recursive call stack of depth n: O(n)
- A 2D table of size n×n (e.g. DP): O(n²)
Iterative vs Recursive Space
C++Same output, but the iterative version uses O(1) space while recursive uses O(n) stack space.
Time-Space Tradeoff
Many optimizations reduce time by using more memory, or reduce memory by accepting slower execution. Memoization is the classic example.
Trading Memory for Speed
Caching previously computed results eliminates redundant work at the cost of extra memory.
- Memoization: store results of expensive calls in an array or map
- Fibonacci with memoization: O(n) time and O(n) space instead of O(2^n) time
- Hash maps give O(1) lookup by trading O(n) extra space
- Precomputed lookup tables are the extreme form of this tradeoff
Memoization: Time-Space Tradeoff
C++The cache vector uses O(n) extra space but reduces time from O(2^n) to O(n).
Amortized Analysis
Amortized analysis spreads the cost of rare expensive operations over a sequence of operations to get an accurate per-operation average. It is commonly used to analyze dynamic arrays.
Amortized Cost
An operation that is occasionally expensive can still be O(1) amortized if the expensive case is rare enough.
- std::vector push_back: usually O(1), but O(n) when the vector doubles its capacity
- Over n pushes, the total work is O(n), so the amortized cost per push is O(1)
- Amortized O(1) does NOT mean every individual call is O(1)
- The capacity doubles at powers of 2, so resizes are rare
Dynamic Array Amortized Cost
C++Resizes happen at powers of 2 only. Most push_backs cost O(1) and the amortized cost is O(1).
Master Theorem for Recurrence Relations
The Master Theorem solves recurrences of the form T(n) = aT(n/b) + f(n) that arise in divide-and-conquer algorithms.
Master Theorem
Given T(n) = aT(n/b) + O(nᵈ), compare d with log_b(a) to find the complexity.
- a = number of subproblems, b = factor by which input shrinks, d = exponent of combine step
- Case 1: d < log_b(a) → O(n^log_b(a)), work dominated by subproblems
- Case 2: d = log_b(a) → O(nᵈ log n), work balanced across levels
- Case 3: d > log_b(a) → O(nᵈ), work dominated by combine step
- Merge Sort: T(n) = 2T(n/2) + O(n), a=2 b=2 d=1, log_2(2)=1 → Case 2: O(n log n)
Merge Sort: O(n log n) by Master Theorem
C++Two subproblems of size n/2 plus an O(n) merge step. Case 2 of the Master Theorem applies.
Knowledge Check
1. What does Big O notation describe?
2. What is the time complexity of accessing an element in an array by index?
3. Which complexity class grows fastest for large n?
4. What is the space complexity of a recursive factorial function with depth n?
5. A nested loop where both loops run n times has what time complexity?
6. What does Big Omega (Ω) represent?
7. A memoized Fibonacci function trades what for speed?
8. What is amortized analysis used for?