Module 01: Time & Space Complexity Analysis
Goal: Master algorithmic complexity from mathematical definitions to real-world hardware behavior. Confidently analyze iterative code, complex recursions, amortized operations, and memory footprints.
Language: C++ (C++17/C++20)
Prerequisites: Basic C++ syntax (loops, functions, recursion).
π Table of Contents
- Asymptotic Notations: The Mathematical Foundation
- Growth Rates Hierarchy
- Iterative Code Analysis Framework
- Amortized Complexity Analysis
- Space Complexity & Memory Layout
- Recurrence Relations & The Master Theorem
- Hidden Complexities & C++ Pitfalls
- Practice Problems with Detailed Solutions
- Top 10 FAANG Interview Questions
1. Asymptotic Notations: The Mathematical Foundation
Asymptotic analysis allows us to describe the resource consumption (execution time or memory) of an algorithm as the input size $n \to \infty$, independent of specific hardware, compiler optimizations, or CPU clock speeds.
Time / Operations
β²
β f(n) = O(g(n)) [Upper Bound]
β /
β cβΒ·g(n) /
β /
β f(n) /
β / /
β cβΒ·g(n) / /
β / /
β / / f(n) = Ξ©(g(n)) [Lower Bound]
β / /
β / /
β / /
β / /
β / /
ββββββββββββββββββββββ΄βββββββββββββββββββββββββΊ Input Size (n)
nβ
[For all n β₯ nβ: cβΒ·g(n) β€ f(n) β€ cβΒ·g(n) β f(n) = Ξ(g(n))]1.1 Big-O Notation ($O$): Asymptotic Upper Bound
$f(n) = O(g(n))$ if there exist positive constants $c > 0$ and $n_0 \ge 1$ such that: $$0 \le f(n) \le c \cdot g(n) \quad \forall n \ge n_0$$ Meaning: In the worst case, the runtime will not grow faster than $g(n)$ scaled by a constant.
1.2 Big-Omega Notation ($\Omega$): Asymptotic Lower Bound
$f(n) = \Omega(g(n))$ if there exist positive constants $c > 0$ and $n_0 \ge 1$ such that: $$0 \le c \cdot g(n) \le f(n) \quad \forall n \ge n_0$$ Meaning: The algorithm requires at least $g(n)$ operations for large $n$.
1.3 Big-Theta Notation ($\Theta$): Asymptotic Tight Bound
$f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$. That is: $$c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \quad \forall n \ge n_0$$ Meaning: The exact rate of growth is tightly bound between $c_1 g(n)$ and $c_2 g(n)$.
1.4 Little-o ($o$) and Little-omega ($\omega$)
- $f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$ (Strict upper bound; $n = o(n^2)$, but $n \ne o(n)$)
- $f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$ (Strict lower bound)
2. Growth Rates Hierarchy
From fastest to slowest running time:
$$O(1) < O(\log \log n) < O(\log n) < O(\sqrt{n}) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$$
βββββββββββββββββ¬ββββββββββββββββββββββββββ¬βββββββββββββββββββββββββββββββββββββββββββ
β Complexity β Name β Typical Example β
βββββββββββββββββΌββββββββββββββββββββββββββΌβββββββββββββββββββββββββββββββββββββββββββ€
β O(1) β Constant Time β Hash map lookup, vector index access β
β O(log n) β Logarithmic Time β Binary search, balanced BST search β
β O(βn) β Square Root Time β Primality test, Square Root Decompositionβ
β O(n) β Linear Time β Array traversal, Kadane's algorithm β
β O(n log n) β Linearithmic Time β Merge Sort, Heap Sort, Quick Sort (avg) β
β O(nΒ²) β Quadratic Time β Nested loops, Bubble / Insertion Sort β
β O(nΒ³) β Cubic Time β Floyd-Warshall, naive matrix multiply β
β O(2βΏ) β Exponential Time β Subset generation, naive Fibonacci β
β O(n!) β Factorial Time β Permutation generation, TSP brute force β
βββββββββββββββββ΄ββββββββββββββββββββββββββ΄βββββββββββββββββββββββββββββββββββββββββββ3. Iterative Code Analysis Framework
Rule 1: Consecutive Statements Add Up
void sequential(int n) {
// Phase 1: O(n)
for (int i = 0; i < n; ++i) {
// O(1) work
}
// Phase 2: O(n^2)
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
// O(1) work
}
}
// Total: O(n + n^2) = O(n^2)
}Rule 2: Nested Loops Multiply (When Independent)
// Outer runs n times, inner runs m times -> O(n * m)
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
doSomething(); // O(1)
}
}Rule 3: Dependent Inner Loops
When the inner loop bound depends on the outer loop variable $i$:
for (int i = 0; i < n; ++i) {
for (int j = i; j < n; ++j) {
doSomething();
}
}Mathematical Count: $$\sum_{i=0}^{n-1} (n - i) = n + (n-1) + (n-2) + \dots + 1 = \frac{n(n+1)}{2} = \frac{n^2}{2} + \frac{n}{2} = \Theta(n^2)$$
Rule 4: Multiplicative Step Sizes (Logarithmic Behavior)
// Step doubles each iteration: 1, 2, 4, 8, ..., 2^k >= n => k = log2(n) iterations
for (int i = 1; i < n; i *= 2) {
doSomething(); // O(1)
} // Total: O(log n)// Nested logarithmic loop
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; j *= 2) {
doSomething();
}
} // Outer runs n times, inner runs log2(n) times -> O(n log n)4. Amortized Complexity Analysis
Amortized analysis guarantees the average performance of each operation in the worst-case sequence of operations.
The Classic Example: Dynamic Array (std::vector) Expansion
When capacity is exceeded, a vector allocates double the capacity, copies $N$ elements, and inserts the new element.
Capacity: 1 [A] Cost: 1
Capacity: 2 [A, B] Cost: 1 (copy) + 1 = 2
Capacity: 4 [A, B, C, _] Cost: 2 (copy) + 1 = 3
Capacity: 4 [A, B, C, D] Cost: 1
Capacity: 8 [A, B, C, D, E, _, _, _]Cost: 4 (copy) + 1 = 54.1 The Aggregate Method
Total cost for $N$ insertions (where $N = 2^k$):
- Regular insertion cost: $N \times 1 = N$
- Copying costs happen at sizes $1, 2, 4, 8, \dots, 2^{k-1}$: $$\text{Total Copies} = 1 + 2 + 4 + 8 + \dots + 2^{k-1} = 2^k - 1 = N - 1$$ $$\text{Total Work} = N + (N - 1) = 2N - 1 = O(N)$$ $$\text{Amortized Cost per operation} = \frac{\text{Total Work}}{N} = \frac{2N - 1}{N} \approx 2 = O(1)$$
4.2 The Accounting (Banker's) Method
- Assign each
push_backan amortized "charge" of $3 credits:- $1 credit pays for the immediate insertion.
- $1 credit is stored with the newly inserted element.
- $1 credit is stored to pay for copying an older element that already spent its credit.
- When resize occurs, every element in the array has $1 credit saved, perfectly paying for its copy to the new array without running out of credits.
5. Space Complexity & Memory Layout
Space Complexity consists of:
- Instruction Space: Compiled machine code.
- Data Space: Constants, global/static variables.
- Dynamic Memory (Heap): Dynamically allocated memory via
new/malloc/ STL containers. - Call Stack Space: Stack frames allocated during function calls and recursion.
Call Stack Depth in Recursion
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}Stack frames built: factorial(n) -> factorial(n-1) -> ... -> factorial(1).
Maximum stack depth = $n \implies \text{Auxiliary Space} = O(n)$.
ββββββββββββββββββββββββββββββββββββββββββ Top of Stack (n=1)
β Stack Frame: factorial(1) [args, ret] β
ββββββββββββββββββββββββββββββββββββββββββ€
β Stack Frame: factorial(2) [args, ret] β
ββββββββββββββββββββββββββββββββββββββββββ€
β ... β
ββββββββββββββββββββββββββββββββββββββββββ€
β Stack Frame: factorial(n) [args, ret] β Bottom of Stack
ββββββββββββββββββββββββββββββββββββββββββ6. Recurrence Relations & The Master Theorem
The Master Theorem Formulation
For divide-and-conquer recurrences of the form: $$T(n) = a T\left(\frac{n}{b}\right) + f(n)$$ where $a \ge 1$, $b > 1$, and $f(n) = \Theta(n^c \log^k n)$ with $k \ge 0$:
Compute the critical exponent: $c_{\text{crit}} = \log_b a$.
| Case | Condition | Solution | Example Algorithm |
|---|---|---|---|
| Case 1 | $c < \log_b a$ (Work dominated by leaves) | $T(n) = \Theta(n^{\log_b a})$ | Strassen's Matrix Mult: $T(n)=7T(n/2)+O(n^2) \implies \Theta(n^{\log_2 7}) \approx \Theta(n^{2.81})$ |
| Case 2 | $c = \log_b a$ (Work evenly distributed) | $T(n) = \Theta(n^c \log^{k+1} n)$ | Merge Sort: $T(n)=2T(n/2)+O(n) \implies \Theta(n \log n)$ |
| Case 3 | $c > \log_b a$ (Work dominated by root) | $T(n) = \Theta(f(n))$ | Binary Search: $T(n)=T(n/2)+O(1) \implies \Theta(\log n)$ |
7. Hidden Complexities & C++ Pitfalls
Pitfall 1: Inefficient String Concatenation
// β BAD: Creates temporary std::string of size i on each iteration
// Total Time: O(1 + 2 + ... + n) = O(n^2)
std::string s = "";
for (int i = 0; i < n; ++i) {
s = s + "a";
}
// β
GOOD: Amortized O(1) per append -> Total O(n)
std::string s = "";
s.reserve(n);
for (int i = 0; i < n; ++i) {
s += 'a'; // or s.push_back('a')
}Pitfall 2: Accidental Pass-by-Value Copies
// β BAD: Copies entire vector of size n on every recursive call!
// Recurrence: T(n) = 2T(n/2) + O(n) copies -> O(n log n) or O(2^n)
void badRecursion(std::vector<int> arr) { ... }
// β
GOOD: Pass by const reference -> O(1) pass
void goodRecursion(const std::vector<int>& arr) { ... }Pitfall 3: std::vector::erase in a Loop
// β BAD: erase from front shifts all remaining elements -> O(n^2)
while (!vec.empty()) {
vec.erase(vec.begin()); // O(k) per erase
}
// β
GOOD: Use std::deque or reverse iterator -> O(n)8. Practice Problems with Detailed Solutions
Problem 1: Analyze Time Complexity of Nested Geometric Loop
#include <iostream>
void complexLoop(int n) {
int count = 0;
for (int i = 1; i <= n; i *= 2) {
for (int j = 1; j <= i; ++j) {
count++;
}
}
std::cout << "Count: " << count << "\n";
}Analysis & Proof:
- Outer loop values of $i$: $1, 2, 4, 8, \dots, 2^k \le n$, where $k = \lfloor \log_2 n \rfloor$.
- Inner loop runs $i$ times for each outer iteration.
- Total iterations: $$\sum_{j=0}^{k} 2^j = 2^{k+1} - 1 \le 2 \cdot 2^{\log_2 n} = 2n = \Theta(n)$$
- Time Complexity: $\Theta(n)$ (Linear, despite nested loops!)
- Space Complexity: $O(1)$
Problem 2: Recurrence Relation for Binary Search
int binarySearch(const std::vector<int>& arr, int low, int high, int target) {
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] > target)
return binarySearch(arr, low, mid - 1, target);
return binarySearch(arr, mid + 1, high, target);
}Analysis:
- Recurrence: $T(n) = T(n/2) + O(1)$, $T(1) = O(1)$.
- Using Master Theorem: $a = 1, b = 2, f(n) = 1 = n^0$.
- $\log_b a = \log_2 1 = 0 = c$.
- Falls under Case 2 ($k = 0$): $T(n) = \Theta(n^0 \log^{0+1} n) = \Theta(\log n)$.
- Time Complexity: $O(\log n)$
- Space Complexity: $O(\log n)$ call stack frames ($O(1)$ if implemented iteratively).
Problem 3: Two-Sum Complexity Comparison
Given an integer array nums and target t:
Approach A: Brute Force
// Time: O(n^2), Space: O(1)
bool twoSumBruteForce(const std::vector<int>& nums, int t) {
int n = nums.size();
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == t) return true;
}
}
return false;
}Approach B: Hash Set
#include <unordered_set>
// Time: O(n) average, Space: O(n)
bool twoSumOptimized(const std::vector<int>& nums, int t) {
std::unordered_set<int> seen;
for (int x : nums) {
if (seen.count(t - x)) return true;
seen.insert(x);
}
return false;
}Problem 4: Matrix Multiplication (Naive vs Divide-and-Conquer vs Strassen)
- Standard 3-Loop Multiplication: $$C_{ij} = \sum_{k=1}^n A_{ik} B_{kj} \implies \Theta(n^3) \text{ time}, \Theta(1) \text{ auxiliary space}$$
- Naive Divide & Conquer: $$T(n) = 8T(n/2) + \Theta(n^2) \implies \log_2 8 = 3 \implies T(n) = \Theta(n^3)$$
- Strassen's Algorithm: $$T(n) = 7T(n/2) + \Theta(n^2) \implies \log_2 7 \approx 2.807 \implies T(n) = \Theta(n^{2.807})$$
Problem 5: Space-Optimized Fibonacci
// Approach A: Naive Recursive -> Time: O(2^n), Space: O(n)
int fibNaive(int n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}
// Approach B: Dynamic Programming -> Time: O(n), Space: O(n)
int fibDP(int n) {
if (n <= 1) return n;
std::vector<int> dp(n + 1);
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= n; ++i) dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}
// Approach C: State Variable Space-Optimized -> Time: O(n), Space: O(1)
int fibOptimized(int n) {
if (n <= 1) return n;
int prev2 = 0, prev1 = 1;
for (int i = 2; i <= n; ++i) {
int curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}9. Top 10 FAANG Interview Questions
Q1: What is the difference between Worst Case, Average Case, and Amortized Worst Case?
Answer:
- Worst Case: The absolute maximum number of operations an algorithm can take for any valid input of size $N$ (e.g., QuickSort on already sorted array with first element as pivot is $O(N^2)$).
- Average Case: The expected number of operations averaged over all possible inputs under a probability distribution (e.g., QuickSort average is $\Theta(N \log N)$).
- Amortized Worst Case: The average cost per operation over a guaranteed worst-case sequence of operations. Unlike average case, it is not probabilistic (e.g.,
vector::push_backis amortized $O(1)$).
Q2: Why does $O(N)$ with large constant factor sometimes run slower than $O(N \log N)$ in practice?
Answer: Asymptotic notation hides constant factors $c$ and lower-order terms. If Algorithm A takes $1000 \cdot N$ CPU cycles (e.g. linked list with cache misses) and Algorithm B takes $2 \cdot N \log_2 N$ (e.g. contiguous vector operations), for $N = 1024$:
- Alg A: $1000 \times 1024 = 1,024,000$ operations.
- Alg B: $2 \times 1024 \times 10 = 20,480$ operations. Hardware cache locality (L1/L2 cache lines of 64 bytes) means contiguous memory access can be 10β50x faster per cycle than chasing heap pointers.
Q3: What is the Space Complexity of Tail-Call Optimized (TCO) recursion?
Answer:
In standard C++, compilers with optimization flags (-O2 / -O3) can optimize tail-recursive functions into iterative jumps (replacing CALL with JMP in assembly), reducing call stack space from $O(N)$ to $O(1)$. However, standard C++ does not guarantee TCO in the language specification (unlike Scheme/Haskell), so portable complexity analysis must assume $O(N)$ unless verified with compiler output.
Q4: Prove that comparison-based sorting algorithms cannot be faster than $\Omega(N \log N)$ in the worst case.
Answer: Any comparison sort can be modeled as a binary decision tree.
- For an array of size $N$, there are $N!$ possible permutations.
- To distinguish all permutations, the decision tree must have at least $N!$ leaves.
- A binary tree of height $h$ has at most $2^h$ leaves: $$2^h \ge N! \implies h \ge \log_2(N!)$$ Using Stirling's Approximation ($\ln(N!) \approx N \ln N - N$): $$h \ge \Omega(N \log N)$$ Since the height represents the worst-case number of comparisons, the lower bound is $\Omega(N \log N)$.
Q5: How do std::unordered_map and std::map compare in Time & Space Complexity?
Answer:
std::unordered_map: Implemented as a Hash Table with separate chaining.- Search/Insert/Delete: Average $O(1)$, Worst case $O(N)$ (hash collisions).
- Space: Higher memory overhead (buckets array + node pointers).
std::map: Implemented as a Self-Balancing Red-Black Tree.- Search/Insert/Delete: Guaranteed $O(\log N)$ worst-case.
- Space: 3 pointers (left, right, parent) + color bit per node. Keys are stored in sorted order.
Q6: Can a function with two nested loops have $O(N)$ time complexity? Give a concrete example.
Answer: Yes. When the inner loop index does not reset to $0$ on each iteration, but advances monotonically. Example: Two-Pointer / Sliding Window:
int left = 0;
for (int right = 0; right < n; ++right) {
while (condition && left <= right) {
left++; // left pointer advances at most n times total across ALL iterations
}
}right increments $N$ times, left increments at most $N$ times. Total operations: $N + N = 2N = O(N)$.
Q7: What is the Master Theorem condition for $T(N) = 2T(N/2) + N \log N$?
Answer:
Here $a = 2, b = 2 \implies \log_b a = 1$.
$f(N) = N \log N = N^1 \log^1 N \implies c = 1, k = 1$.
Since $c = \log_b a$, this falls under Case 2 with $k = 1$:
$$T(N) = \Theta(N^{\log_b a} \log^{k+1} N) = \Theta(N \log^2 N)$$
Q8: What is Auxiliary Space vs Total Space?
Answer:
- Total Space: Total memory required by the program, including input data, output data, and temporary working storage.
- Auxiliary Space: Extra space or temporary memory allocated by the algorithm excluding the input and output sizes. When interviewers ask for space complexity, they almost always refer to Auxiliary Space.
Q9: Why is dynamic array resizing factor 2.0 or 1.5 instead of 3.0 or 10.0?
Answer:
- A growth factor of $2.0$ or $1.5$ gives amortized $O(1)$ push back while keeping memory overhead within reasonable bounds ($\le 50%$ or $100%$ wasted space).
- A factor like $1.5$ (used in MSVC STL and
folly::fbvector) allows previously deallocated blocks of memory to be reused in future reallocations, minimizing memory fragmentation and OS page faults.
Q10: What is the time complexity of building a heap from an unsorted array of size $N$?
Answer:
$O(N)$, not $O(N \log N)$.
Bottom-up buildHeap invokes siftDown from level $\lfloor N/2 \rfloor$ down to $0$. The number of nodes at height $h$ is at most $\lceil N / 2^{h+1} \rceil$, and each sift-down takes $O(h)$ steps.
$$\text{Total Work} = \sum_{h=0}^{\log N} \frac{N}{2^{h+1}} O(h) = \frac{N}{2} \sum_{h=0}^{\log N} \frac{h}{2^h} = O(N)$$
Since $\sum_{h=0}^\infty \frac{h}{2^h} = 2$, total work is $O(N)$.