Mastering Time and Space Complexity Analysis
Introduction: What Are Time and Space Complexity?
When we analyze an algorithm, we want to describe how its running time and memory usage grow as the input size grows. This is where time complexity and space complexity come in. In simple terms:
Time Complexity measures how long an algorithm runs as a function of input size ( Mastering Time and Space Complexity in DSA: Your Ultimate Guide - DEV Community).
Space Complexity measures how much extra memory (besides the input) an algorithm uses as a function of input size ( Mastering Time and Space Complexity in DSA: Your Ultimate Guide - DEV Community).
We use Big O notation to express these complexities, focusing on the dominant growth term and ignoring constants. For example, if an algorithm takes at most 3n^2 + 10n + 5 operations for input of size n, we say its time complexity is O(n²)(drop the constants and lower-order terms) (How to find time complexity of an algorithm? | Adrian Mejia Blog). Big O gives an upper bound on growth, usually in the worst case scenario (How to find time complexity of an algorithm? | Adrian Mejia Blog). (Sometimes we analyze average or best cases, but unless stated otherwise, assume Big O refers to worst-case.)
Common Complexity Classes: Here are some common time complexity classes in increasing order of growth:
O(1) – Constant time: runtime does not depend on input size (e.g. accessing one array element).
O(log n) – Logarithmic: grows slowly, often from algorithms that divide the problem in half (like binary search).
O(n) – Linear: grows directly proportional to input size (e.g. looping through an array of n elements).
O(n log n) – Linearithmic: typically from divide-and-conquer algorithms that solve subproblems and merge results (e.g. merge sort).
O(n^2) – Quadratic: often from a double nested loop over n items (e.g. comparing all pairs).
O(2^n) – Exponential: runtime doubles with each additional input element (e.g. naive recursive Fibonacci).
O(n!) – Factorial: grows even faster, often from generating all permutations of n items.
(How to find time complexity of an algorithm? | Adrian Mejia Blog) Visualization of how different time complexities grow as input size increases. Higher complexity classes (like exponential or factorial) skyrocket even for modest n, whereas linear or logarithmic grow much more slowly.
Space complexity classes (O(1), O(n), O(n^2), etc.) are interpreted similarly, but for memory. For instance, an algorithm that uses only a fixed number of variables is O(1) space, whereas one that allocates an array of size n is O(n) space.
Why it Matters: Understanding these complexities lets us predict if an algorithm will run efficiently for large inputs. For example, an O(n log n) sorting algorithm will outperform an O(n^2) sorting algorithm for large n. In interviews and optimization work, you’ll need to confidently determine these complexities and choose appropriate algorithms.
In this guide, we’ll start from fundamental patterns (like simple loops) and build up to advanced techniques (like divide-and-conquer, dynamic programming, graph traversals, etc.). For each concept, we’ll develop a mental model to recognize the pattern in real code, break down how to analyze it step-by-step, identify common pitfalls, and solidify understanding with progressively challenging examples. By the end, you should be able to determine time and space complexity for any algorithm with intuition rather than rote memorization ( Mastering Time and Space Complexity in DSA: Your Ultimate Guide - DEV Community).
Let’s begin our deep dive, starting with straightforward iterative code and then ramping up!
Iterative Code: Analyzing Loops and Sequential Operations
Iterative code uses loops (for, while, etc.) to repeat operations. Analyzing iterative complexity is often about counting loop iterations and understanding whether loops run in sequence or are nested.
Mental Model: Each loop or repetition contributes to time complexity proportional to its number of iterations. Sequential (non-nested) loops add their complexities, while nested loops multiply them ( Mastering Time and Space Complexity in DSA: Your Ultimate Guide - DEV Community). We drop constant factors and focus on the highest-order term.
Key Patterns for Iterative Code:
A loop that runs a fixed number of times (e.g. 100 iterations regardless of n) is O(1) – constant time (How to find time complexity of an algorithm? | Adrian Mejia Blog).
A loop that runs in proportion to n (e.g.
for i from 1 to n) is O(n) (How to find time complexity of an algorithm? | Adrian Mejia Blog).If you have two back-to-back loops, each O(n), the total is O(n + n) = O(2n), which simplifies to O(n) (linear) (How to find time complexity of an algorithm? | Adrian Mejia Blog).
If a loop index grows or shrinks by a constant fraction each time (like
i *= 2or halving the range), the loop is O(log n) because it runs only about log₂(n) times (How to find time complexity of an algorithm? | Adrian Mejia Blog).Nested loops: we’ll cover in the next section, but note that a loop inside another multiplies complexity (e.g. an inner O(n) loop inside an outer O(n) loop yields O(n·n) = O(n²) ( Mastering Time and Space Complexity in DSA: Your Ultimate Guide - DEV Community)).
Step-by-Step Analysis for Iterative Code:
Count Iterations: Determine how many times the loop(s) execute in terms of n. For example,
for (i=0; i<n; i++)runs n times → O(n). A while loop doublingieach time runs ~log₂(n) times → O(log n).Identify Sequential vs Nested: If loops are one after another, add their counts (which means take the max order in Big O). If one loop is inside another, multiply their counts (nested).
Consider Loop Conditions and Increments: e.g. looping to n/2 is still O(n) (just 0.5n iterations, constant factor) (How to find time complexity of an algorithm? | Adrian Mejia Blog). Looping by 2 (i+=2) is also O(n) (0.5n steps) (How to find time complexity of an algorithm? | Adrian Mejia Blog).
Drop constants and lower terms: e.g. if one loop is O(n) and the next is O(n), O(n) + O(n) = O(2n) simplifies to O(n) (algorithm - Why is merge sort worst case run time O (n log n)? - Stack Overflow). If one part is O(n) and another is O(n²), overall is O(n²) (n² dominates for large n).
Space complexity in iterative code is often determined by data structures used. A loop itself typically uses O(1) space (just loop counter variables) unless it creates new arrays or lists.
Identifying Iterative Patterns in Real Code
Some clues that indicate a piece of code runs in linear time (O(n)) or similar: a single for or while loop iterating n times, using arithmetic progression. If you see a loop, ask "how many iterations will this perform relative to input size?"
Linear scan – iterating through an array or list once -> O(n).
Partial loop – e.g. loop from 0 to n with break conditions: worst-case still O(n) (best-case could be less).
Double iteration by a constant – e.g.
for (int i=0; i<n; i+=5)is O(n) (just fewer iterations by constant factor).Logarithmic loop – e.g.
while (n > 0) { n = n/2; }is O(log N) because n is halved each time.Amortized patterns – sometimes a loop inside a loop isn’t nested but sequential over the input (like two-pointer techniques); we’ll discuss those later.
Tips & Tricks (Iterative):
A loop that counts down from n to 1 is O(n) just like counting up.
A loop that runs, say, n/2 times is O(n) (constants like 1/2 are dropped) (How to find time complexity of an algorithm? | Adrian Mejia Blog).
Watch out for loops that depend on input values (e.g. loop until a value becomes 0 by subtracting 5 each time – that’s still proportional to n).
If an array of size n is processed element by element, that’s O(n) time and O(1) extra space (if just reading/updating in place).
Always consider the worst-case number of iterations when evaluating Big O (unless asked for average-case).
Red flag: an uncontrolled loop that might repeat n times for each of n elements (that would be n*n = n² – see next section on nested loops).
Now, let’s apply these to concrete examples, increasing in difficulty and highlighting complexity reasoning and pitfalls.
Example 1: Constant Time Operation
// Problem: Return the first element of an array
function getFirstElement(arr) {
return arr[0]; // Access the first element
}
Complexity Analysis: Accessing an array element by index is a single operation in JavaScript – it doesn’t depend on array length. So this function runs in O(1) time (constant time). Space complexity is O(1) as well, since it uses no additional space beyond a few variables.
Step-by-Step Reasoning: Regardless of array size, we do one index lookup. Even if arr had 1 million elements, arr[0]is a direct access in constant time.
Common Mistake: Some might think this is O(n) because there are n elements in the array, but merely accessing one element does not loop through all elements. The operation cost is fixed ( Mastering Time and Space Complexity in DSA: Your Ultimate Guide - DEV Community).
Example 2: Linear Time Loop (O(n))
// Problem: Compute the sum of all numbers in an array
function sumArray(arr) {
let sum = 0;
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
}
return sum;
}
Approach: We iterate through each array element and accumulate a sum.
Time Complexity: O(n) – The for-loop runs n times (where n = arr.length). Each loop iteration does O(1) work (addition and indexing), so total time is proportional to n (How to find time complexity of an algorithm? | Adrian Mejia Blog).
Space Complexity: O(1) – We use a couple of variables (sum and i), but no additional arrays or structures proportional to n.
Step-by-Step: If the array has 10 elements, we do 10 additions. If it has 1,000, we do 1,000 additions. The work grows linearly with the number of elements. We add up complexities: here it’s just one loop. No nested loops, so it’s straightforward.
Pitfall: Sometimes people include the addition inside as another factor, thinking O(n*1) = O(n) (which is correct but the *1 is unnecessary detail). Just note the inner operations are constant time each.
Common Mistake: Stopping the loop early if a condition met would change best-case time, but worst-case still O(n). Here we loop through all elements unconditionally.
Example 3: Loop with Early Termination (Worst-Case Linear)
// Problem: Find a number in an array; return true if found, false otherwise
function contains(arr, target) {
for (let element of arr) {
if (element === target) {
return true; // found early, can return
}
}
return false; // not found after checking all
}
Approach: Linearly scan through the array until the target is found.
Time Complexity: O(n) in the worst case. In the best case, the target might be at the first position (then it's O(1) best-case). But Big O usually denotes worst-case: if the target isn’t present or is at the end, we check all n elements => O(n).
Space Complexity: O(1) – only uses a couple of variables.
Step-by-Step: We examine each element sequentially and potentially break out early. The worst-case scenario (target not present or last element) requires n checks. Early return doesn’t improve the worst-case complexity; it only improves average-case if targets are often near the front.
Common Mistake: Assuming this is always O(1) because “we might return early.” The upper bound is still linear. Interviewers often expect understanding of worst vs average case here.
Mistake 2: A subtle one: forgetting to account for the loop at all if you see an if inside – but that if is inside the loop that runs n times at worst.
Red Flag: If this function were called on a huge list repeatedly in a worst-case scenario (target not found), it could be slow. But it's optimal for an unsorted list (you must examine each element in worst case).
Example 4: Multiple Sequential Loops (Adding Complexities)
// Problem: Print all elements of two arrays (separately)
function printArrays(arr1, arr2) {
// Loop over first array
for (let x of arr1) {
console.log(x);
}
// Loop over second array
for (let y of arr2) {
console.log(y);
}
}
Approach: We have two independent loops, one over arr1 and one over arr2.
Time Complexity: O(n + m) (if n is length of arr1 and m is length of arr2). If we consider overall input size N = n+m, this is O(N). In Big O, if one array dominates, we might simplify to O(max(n, m)). If we assume arr2’s size is proportional to arr1 (say both ~n), then O(n + n) = O(n) (How to find time complexity of an algorithm? | Adrian Mejia Blog). The key is the loops are not nested, they happen sequentially, so we add their costs ( Mastering Time and Space Complexity in DSA: Your Ultimate Guide - DEV Community).
Space Complexity: O(1) – just loop counters and constants.
Breakdown: First loop: O(n). Second loop: O(m). Total = O(n) + O(m). We do not multiply because these loops are not nested; they run one after the other. In Big O notation, if we don't know the relationship between n and m, we keep both: O(n+m). Often we say O(n) if m is considered another input parameter of similar scale.
Tip: If arr2 was, say, always of size 100 (constant), then the second loop is O(1) and overall would be O(n + 1) = O(n). But here assume generic sizes.
Common Mistake: Some novices might erroneously multiply because they see two loops. But remember: multiply for nested, add for sequential ( Mastering Time and Space Complexity in DSA: Your Ultimate Guide - DEV Community). Here they are sequential, so not O(n*m).
Example 5: Loop with Non-Standard Increment (Still Linear)
// Problem: Print every 5th element of an array
function printEveryFifth(arr) {
for (let i = 0; i < arr.length; i += 5) {
console.log(arr[i]);
}
}
Time Complexity: O(n) – The loop jumps in steps of 5. If array length is n, it will execute roughly n/5 times, which is still O(n) (constant factor 1/5 is dropped) (How to find time complexity of an algorithm? | Adrian Mejia Blog). For example, if n=100, this loop runs ~20 times; if n=1,000, runs ~200 times. It grows linearly with n.
Space Complexity: O(1).
Notes: Even though we skip most elements, Big O cares about the scale as n grows. Dividing work by a constant factor (5 in this case) doesn’t change the asymptotic class.
Common Mistake: Thinking fewer iterations (like n/5) might be O(n/5) and somehow “less” than O(n). But by definition O(n/5) = O(n) because Big O ignores constant multipliers (How to find time complexity of an algorithm? | Adrian Mejia Blog). Similarly, a loop by 2 (half iterations) is still O(n). Only if the loop grows/shrinks proportionally to n (i.e., linear in n) or a fraction of n, it’s O(n). (If it shrinks exponentially like multiplying index by 2, that’s different – see next example.)
Example 6: Logarithmic Loop (O(log n))
// Problem: Repeatedly divide n by 2 until it becomes < 1
function repeatedlyHalve(n) {
let count = 0;
while (n >= 1) {
n = n / 2;
count++;
}
return count;
}
What it Does: This loop counts how many times we can halve n until it drops below 1.
Time Complexity: O(log n) – Each iteration cuts n in half. The number of iterations is about ⌊log₂(n)⌋+1. For example, if n=16, loop runs 5 times (16→8→4→2→1); if n=1,000,000 (~2^20), loop runs ~20 times. Generally, halving repeatedly yields a logarithmic number of steps (How to find time complexity of an algorithm? | Adrian Mejia Blog). We can say time complexity is O(log₂ n), and base of log doesn’t matter in Big O (constant factor), so O(log n).
Space Complexity: O(1).
Step-by-Step: After k iterations, n becomes ~n/(2^k). The loop ends when n/(2^k) < 1 ⇒ 2^k > n ⇒ k > log₂(n). So k ≈ ⌈log₂ n⌉. That grows much slower than n. For n=1e6, k≈20; for n=1e9, k≈30.
Pitfall: Ensure you identify this as a logarithmic pattern. Some might think since we decrement (actually dividing) in a loop until a condition, it could be linear. But because the decrement is multiplicative (n = n/2) rather than subtractive (n = n-1), it’s a shrinking geometric series.
Common Mistake: Ignoring how the loop variable changes. If it were n -= 2 each time, that’s still linear O(n). But n /= 2 is different – leads to log behavior. Always consider: how many times can I do this operation before the loop ends?
Example 7: Amortized Linear - Two-Pointer in One Pass
// Problem: Move all zeros in an array to the end, preserving order of nonzeros.
function moveZerosToEnd(arr) {
let write = 0; // index to write non-zero
for (let read = 0; read < arr.length; read++) {
if (arr[read] !== 0) {
// swap non-zero element to the 'write' position
[arr[write], arr[read]] = [arr[read], arr[write]];
write++;
}
}
}
Approach: This uses two indices (read and write). read scans through the array, and write lags behind to mark where the next non-zero should be placed. Essentially, each element is visited a constant number of times.
Time Complexity: O(n) – We have a single loop from read=0 to n-1. Inside, swapping and comparisons are O(1). So it’s linear in n.
Space Complexity: O(1) – In-place swaps, using only a couple of index variables.
Amortized Analysis: Notice some elements might be swapped multiple times, but each element is moved at most once or twice. Precisely, each element is read once by read. The write index only moves forward and each element is swapped at most once when it’s first encountered as non-zero. So total operations are bounded by some constant * k * n (with k small, here <=3 operations per element), hence still linear.
Common Pitfall: For two-pointer techniques, sometimes people worry if inner operations (like multiple swaps) might increase complexity. The key is to ensure each element isn’t involved in too many operations. Here, swap happens for non-zero elements, each such element gets swapped exactly once into its rightful position. The zeros accumulate at end without extra full passes.
Identifiable Pattern: Two pointers moving in one pass often implies O(n) because each pointer traverses the array at most once (or one pointer does full traversal while the other lags or leads but overall operations ~2n, which is O(n)). We’ll cover more in the dedicated two-pointer section, but it’s introduced here as an iterative scenario.
Mistake: A less efficient approach might have been nested loops (for each element, if it’s zero, find next non-zero to swap – that would be O(n^2)). The above is optimized to O(n). Not recognizing the pattern could lead to writing a quadratic solution unnecessarily.
With these examples, we saw how to analyze loops and sequential operations. The mental checklist: How many times does this run in the worst case? Are loops nested or sequential? Does the loop divide the problem (log) or iterate linearly? These determine the Big O.
Next, we move to a related concept: nested loops and nested structures, which often lead to polynomial (quadratic, cubic, etc.) time complexities.
Nested Structures: Analyzing Nested Loops and Iterations
When loops are nested—one inside another—the total work often multiplies. This leads to complexities like O(n²), O(n*m), O(n³), etc., depending on how the nesting occurs. Nested iterations commonly arise when dealing with pairwise comparisons, matrices, or multiple dimensions of data.
Mental Model: For nested loops, try to interpret it as: for each iteration of the outer loop, the inner loop runs fully. Multiply the iteration counts of outer and inner loops to get total iterations ( Mastering Time and Space Complexity in DSA: Your Ultimate Guide - DEV Community). If loops are nested three deep, multiply all three counts. Then simplify the expression to Big O.
Common Patterns:
Double nested loop over same range:
for i in 1..n: for j in 1..n: // constant workHere outer runs n times, inner runs n times for each outer -> total n * n = O(n²) ( Mastering Time and Space Complexity in DSA: Your Ultimate Guide - DEV Community).
Double loop over different ranges: e.g. outer loops m times, inner loops n times -> O(n * m). If m ~ n, that’s O(n²). If m is a constant, then it’s O(n).
Tripe nested loop: O(n³) (and so on for more nests).
Nested with dependent range: e.g. inner loop from i to n (shrinks as i increases). That yields approximately n + (n-1) + ... + 1 operations = n(n+1)/2 = O(n²) (still quadratic). Triangular loops are still quadratic, just half the pairs.
Nested where inner loop is smaller scale: e.g. outer n, inner loop runs 10 iterations (constant) -> O(n * 10) = O(n). Or inner loop runs log n while outer runs n -> O(n log n). (Not all nested loops are polynomial; one loop can be smaller.)
Nested two-pointer patterns: sometimes one index moves forward while another moves backward in a single nested structure, resulting in linear overall (like the typical two-pointer summing which we’ll discuss separately).
Step-by-Step Analysis for Nested Loops:
Identify the outer loop’s complexity (in terms of n).
Identify the inner loop’s complexity (how many iterations for each outer iteration?). If the inner loop runs a fixed number or a function of the outer index.
Multiply the two counts to get total iterations (How to find time complexity of an algorithm? | Adrian Mejia Blog).
Add up contributions if there are separate independent nested loops in sequence (though often we analyze each nested block separately).
Simplify to Big O.
Tip: Think of a nested double loop as iterating over all pairs (i, j). If i runs n times and j runs m times for each i, that’s n*m total pairs checked.
Space complexity for nested loops is usually still O(1) (just counters) unless you allocate a structure like an n×n matrix (which would be O(n²) space).
Now, let’s walk through examples from basic to tricky nested patterns:
Example 8: Simple Nested Loop (O(n²))
// Problem: Print all pairs of elements from an array
function printAllPairs(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
console.log(arr[i], arr[j]);
}
}
}
What it Does: It prints each possible pair (including a pair of an element with itself when i==j).
Time Complexity: O(n²) – The outer loop runs n times. For each outer iteration, the inner loop runs n times ( Mastering Time and Space Complexity in DSA: Your Ultimate Guide - DEV Community). Total = n * n = n² prints. If n=100, that’s 10,000 operations; if n=1000, that’s 1,000,000 (one million) operations.
Space Complexity: O(1) – Only uses loop indices.
Step-by-Step: Outer i from 0 to n-1. For a fixed i, inner j goes 0 to n-1. So it prints (i,0), (i,1), ..., (i,n-1). It does that for each i. So total pairs = n * n. We drop constants (the exact number of print operations is n²) and lower terms (there are none in this case) to get O(n²).
Common Mistake: Thinking this might be O(n) because “two loops” might confuse (some guess O(2n) incorrectly). But here they are nested, not sequential. Always multiply for nested loops ( Mastering Time and Space Complexity in DSA: Your Ultimate Guide - DEV Community).
Note: This prints ordered pairs (including self-pairs and reversed pairs separately). If one wanted unique unordered pairs i<j, the inner loop could start from i+1, which we’ll see next.
Example 9: Triangular Nested Loop (O(n²) as well)
// Problem: Print all unique pairs (i, j) from array (i < j)
function printUniquePairs(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
console.log(arr[i], arr[j]);
}
}
}
What it Does: For each pair of indices (i, j) with i < j, it prints that pair once. This avoids duplicate/reversed pairs.
Time Complexity: O(n²) – It’s roughly half of the previous double loop’s iterations, but Big O still n(n-1)/2 = O(n²). The dominant term is n²/2, which simplifies to n² by dropping the constant 1/2 factor.
Space Complexity: O(1).
Analysis: Outer loop runs n times. The inner loop does: (n-1) + (n-2) + ... + 1 iterations over the course of outer loop. This sum = n(n-1)/2 ≈ 0.5 n² - 0.5 n. Dropping constants/low-order terms -> O(n²).
Important Insight: Even though the inner loop shrinks each time (as i grows, j starts later), the overall order remains quadratic. The work is like summing an arithmetic series which yields a quadratic function of n.
Common Mistake: Some might attempt to approximate and worry "but it's half of n², so maybe something different?" No, in Big O we drop constant fractions.
Pitfall: If n is large, this is still significant. E.g., n=10000, operations ~ 50 million. This is why quadratic can be problematic for large n.
Use Case: This pattern appears in checking all pairs (like two-sum brute force, checking all combinations of 2, etc.).
Example 10: Nested Loops with Different Lengths (O(n * m))
// Problem: Count how many times an element of arr1 appears in arr2
function countMatches(arr1, arr2) {
let count = 0;
for (let x of arr1) {
for (let y of arr2) {
if (x === y) {
count++;
}
}
}
return count;
}
What it Does: For each element in arr1, it loops through arr2 to count matches. (This is essentially a double loop over two arrays of possibly different lengths.)
Time Complexity: O(n * m) – Let n = length of arr1, m = length of arr2. The outer loop runs n times, inner runs m times for each (How to find time complexity of an algorithm? | Adrian Mejia Blog). So total comparisons = n * m. In Big O, we keep it as O(n*m) if we want to be general. If arr1 and arr2 are of comparable size, this becomes O(n²). If one is much smaller, the complexity is proportional to the product.
Space Complexity: O(1).
Example: If arr1 has 100 items and arr2 has 1000 items, that’s 1001000 = 100k checks. If both had n items, it’s nn = n².
Tip: Use O(n*m) notation for two-input problems. If an algorithm’s complexity depends on two independent input sizes, mention both.
Common Mistake: Multiplying incorrectly or assuming n==m implicitly. If they are distinct, express complexity with two variables.
Optimization Thought: If one array were sorted, we could potentially use faster search (like binary search in inner loop, O(log m) each, making overall O(n log m)). Or use a hash set for one array to achieve average O(n + m) matching. But given this brute-force approach, O(n*m) is correct.
Example 11: Triple Nested Loop (O(n³))
// Problem: Print all triplets (i, j, k) from array
function printTriplets(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
for (let k = 0; k < arr.length; k++) {
console.log(arr[i], arr[j], arr[k]);
}
}
}
}
Time Complexity: O(n³) – Three nested loops, each goes up to n. Total combinations (i,j,k) = n * n * n = n³.
Space: O(1).
Discussion: This is obviously expensive for large n. If n = 100, that’s 1,000,000 prints; if n = 1000, that’s 1 billion prints – totally infeasible. Often triple nested loops appear in naive solutions to 3-sum or checking triplets, etc., and usually need optimization for bigger inputs.
Common Mistake: Similarly, not recognizing triple nest multiplies thrice. It's straightforward here.
Note: If loops had different lengths (n, m, p), complexity would be O(nmp).
Example 12: Nested Loop with Independent Inner Work (constant inner loop)
// Problem: For each element in array, perform a fixed number of constant-time operations
function processWithFixedSteps(arr) {
for (let i = 0; i < arr.length; i++) {
// inner loop runs a constant 100 times
for (let j = 0; j < 100; j++) {
doConstantWork(i, j);
}
}
}
Time Complexity: The outer loop is O(n). The inner loop runs 100 times for each i, which is O(1) (constant) work relative to n (100 is constant). Total = n * 100 -> O(n).
Space: O(1).
Explanation: Even though it’s nested syntactically, the inner loop is not dependent on input size (always 100 iterations). Therefore, complexity is O(n * 1) = O(n).
This highlights: not every nested loop implies polynomial complexity. If the nesting level has a constant bound, it contributes a constant factor.
Common Mistake: Seeing two loops and saying O(n²) without noticing the inner loop doesn’t scale with n. Always consider loop bounds carefully.
Real-world example: An algorithm that, for each item, does some fixed set of calculations (say check up to 100 related possibilities). That’s still linear overall.
Example 13: Nested Loop with Logarithmic Inner Loop (O(n log n))
// Problem: For each element, repeatedly divide it by 2 until it becomes 0.
function processAndHalve(arr) {
for (let x of arr) {
let value = x;
while (value > 0) {
value = Math.floor(value / 2);
// do O(1) work with value
}
}
}
Analysis: Outer loop runs n times (for each element in arr). Inner loop runs O(log V) where V is the value of x, because it halves the value each time. In worst case, if x is on the order of the largest input value M, the inner loop is O(log M). So one might say complexity is O(n log M). If we assume values are not exponentially large relative to n (or simply treat log M as some function), often this is simplified to O(n log n) in contexts where values scale with n. But to be precise, it's O(n log M).
If we treat the magnitude of numbers as another parameter, we keep it separate: O(n * log M). If numbers are, say, up to n, then it becomes O(n log n). If they are up to 2^k, then log M = k, so O(n * k).
For simplicity here, let's assume values are roughly related to n or at least treat log M as a secondary factor. The pattern of linear times log yields O(n log n) complexity.
Space: O(1).
Key Point: A loop inside another doesn’t always yield n*n. Here it’s n * (log of something). This pattern frequently appears in algorithms like sorting (n log n), where one loop (or recursion) is log n deep and another is n wide.
Common Mistake: Not recognizing the inner loop is logarithmic and thinking maybe it's constant or linear. Each valuegets halved until it’s 0, which is proportional to log2(value). On average, if values vary, complexity analysis might need expected log of values, but worst-case if a value ~N, then O(log N).
Example 14: Combination of Nested and Sequential Loops
// Problem: Do a quadratic loop, then a linear loop
function mixedLoops(n) {
// Quadratic part
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
doWork(i, j); // O(1) work
}
}
// Separate linear part
for (let k = 0; k < n; k++) {
doAnotherWork(k); // O(1) work
}
}
Time Complexity: The first nested loop is O(n²). The second loop is O(n). Total complexity = O(n² + n). For large n, n² dominates n, so this is O(n²) (algorithm - Why is merge sort worst case run time O (n log n)? - Stack Overflow). We addthe two parts because they happen sequentially, not one inside the other.
Space: O(1).
Explanation: Even though there’s an extra linear loop after the quadratic one, in Big O we drop the lower-order term (n is lower order compared to n²). It’s important to mention both during analysis, but final answer is O(n²).
Common Mistake: Ignoring the smaller term’s existence. It’s good to note it, but in Big O simplest form, O(n² + n) = O(n²). So the highest-order term prevails (algorithm - Why is merge sort worst case run time O (n log n)? - Stack Overflow).
Key Takeaway: When multiple segments of code are executed in sequence, find the complexity of each and then take the one that grows fastest as n → ∞. Only if complexities are incomparable (like O(n²) + O(m) for different inputs) would you keep them separate.
Tips & Tricks (Nested loops):
If you see a loop inside a loop, expect polynomial growth (multiplying factors). Check if inner loop’s range depends on the outer loop variable or is independent.
Triangular loops (inner loop starts at i+1 or similar) still yield quadratic complexity, though roughly half the operations of full n². Big O doesn’t distinguish the constant 1/2 difference (algorithm - Why is merge sort worst case run time O (n log n)? - Stack Overflow).
If dealing with matrices: iterating a 2D grid of n×m is O(n*m). A 3D grid of n×n×n is O(n³).
Breaking out of inner loops: If in worst case you don’t break out, still treat as full nest. If break always happens very early, that might reduce average, but worst-case often remains full run unless we can bound it otherwise.
Nested recursion: We haven’t touched – that often leads to exponential. We’ll see recursion trees for those.
Now that we’ve covered iterative patterns, both sequential and nested, let's move on to recursion – where complexity can sometimes be less obvious and often solved via recurrence relations or recursion trees.
Recursive Code: Analyzing Basic Recursion Patterns
Recursive algorithms call themselves to solve subproblems. The complexity analysis often involves solving a recurrence relation: T(n) = ... in terms of T(smaller input). For straightforward recursion (like a function calling itself once per call), the complexity is usually proportional to the number of calls in the recursion tree.
Mental Model: Think of recursion as building a call tree. Each function call may spawn other calls. The total time is essentially (number of recursive calls) * (cost per call). We derive the count of calls by understanding how the recursion progresses and stops.
Key Recursive Patterns:
Linear Recursion (Tail Recursion): The function calls itself once per step, moving towards the base case by a constant amount (e.g. n-1 each time). This results in O(n) calls. Example: factorial, or summing an array with recursion. Each call does O(1) work plus one recursive call, so T(n) = T(n-1) + O(1) which solves to O(n)(Analyzing Time and Space Complexity in Recursive Algorithms).
Multiple Recursion (Branching): The function calls itself multiple times. For example, Fibonacci naive: T(n) = T(n-1) + T(n-2) + O(1). This yields exponential growth because the same subproblems get recomputed many times. A recursion that splits into two independent subcalls of nearly the same size often results in O(2^n) complexity (Analyzing Time and Space Complexity in Recursive Algorithms). Branching factor b = 2 with depth ~n gives ~2^n calls (actually ~φ^n for Fibonacci, but that’s still exponential).
Divide and Conquer Recursion: This is a special case we’ll handle more in the next section. It calls itself on fractions of the input (like half each time). E.g. binary search: T(n) = T(n/2) + O(1) -> O(log n). Or merge sort: T(n) = 2T(n/2) + O(n) -> O(n log n). We usually solve these by the Master Theorem or recursion tree.
Recursion with Overlapping Subproblems: This is where dynamic programming comes in to avoid recomputation. For now, naive recursion that revisits subproblems (like Fibonacci) is exponential, but if you memoize results, it can drop to linear. We’ll cover memoization later.
For basic recursive code analysis, a trick is to unroll a few levels or visualize the call tree:
If it looks like a chain of calls depth n (one call to next), it’s O(n).
If it splits and doubles the calls each level (like fib), that’s O(2^n).
If it splits but into uneven parts or one branch doesn't always call, adjust accordingly (but worst-case often similar pattern).
Also consider the space complexity: recursion uses a call stack. A recursion depth of k uses O(k) stack space. So a linear recursion depth n uses O(n) space. Branching recursion still uses O(depth) stack at any given time (one branch at a time, unless parallel). For example, naive Fibonacci recursion has depth n (it goes down to fib(1) along one branch), so uses O(n) stack space, even though time is O(2^n). Contrast: divide and conquer like mergesort has depth O(log n), so call stack space O(log n). We should account for this in space complexity.
Let’s analyze some fundamental recursion examples:
Example 15: Factorial (Linear Recursion)
// Problem: Compute n!
function factorial(n) {
if (n === 0 || n === 1) {
return 1; // base case
}
return n * factorial(n - 1);
}
Time Complexity: O(n) – The function calls itself once for each decrement of n. It will make n recursive calls (actually n-1 calls until hitting base case). So T(n) = T(n-1) + O(1), solve to T(n) = O(n) (Analyzing Time and Space Complexity in Recursive Algorithms). For example, factorial(5) calls factorial(4), which calls 3,2,1 – five total multiplications (which is proportional to n).
Space Complexity: O(n) – Each recursive call adds a layer to the call stack. The deepest call happens at n=0 base case, with n frames on the stack. So it uses linear stack space.
(Analyzing Time and Space Complexity in Recursive Algorithms) gives the reasoning: in factorial, the number of multiplications (or recursive calls) is proportional to n, so time grows linearly with n.
Common Mistake: Some think recursion is “slower” by some constant overhead, but in Big O we ignore constant factors. So recursive factorial is O(n) just like an iterative loop for factorial would be O(n). The overhead of function calls is constant per call.
Pitfall: If n is large (say 10000), this will cause a deep recursion which could risk stack overflow if beyond recursion limit of environment. Complexity-wise it's fine O(n), but practically tail recursion optimization (TCO) could help if language supported (JS does not reliably do TCO). If we care about that, an iterative approach might be safer. But complexity remains O(n).
Example 16: Sum of Array (Recursive Linear)
// Problem: Recursively compute sum of array elements
function recursiveSum(arr, index = 0) {
if (index === arr.length) return 0; // base: no elements
return arr[index] + recursiveSum(arr, index + 1);
}
Time Complexity: O(n) – It will make one recursive call per element. Essentially a linear scan via recursion. T(n) = T(n-1) + O(1) like before -> O(n).
Space Complexity: O(n) – Depth of recursion = n (worst case we go all the way to end of array). So stack holds n calls.
Note: This is equivalent to an iterative loop summing the array. It’s just done recursively.
Common Mistake: Counting the addition operations separately, but they are all encompassed in those n calls. Each call does one addition (except base does none). So total ~n additions, O(n).
Pitfall: If arr is huge, recursion could blow stack in JS, whereas iterative wouldn’t. That’s an implementation detail, not complexity.
Example 17: Binary Search (Recursive Logarithmic)
// Problem: Binary search for target in sorted array
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
if (left > right) {
return -1; // not found
}
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
return binarySearch(arr, target, mid + 1, right);
} else {
return binarySearch(arr, target, left, mid - 1);
}
}
Time Complexity: O(log n) – Each recursive call halves the search range (approximately). If array length is n, we check mid and then search either left half or right half (size ~n/2). So T(n) = T(n/2) + O(1). This recurrence solves to O(log₂ n) (How to find time complexity of an algorithm? | Adrian Mejia Blog). For example, searching in a 128-element array would at most take 7 calls (since 2^7=128). The recursion depth is log₂(n) (rounded up).
Space Complexity: O(log n) – The recursion depth (call stack) in worst case is log₂(n) because each call goes one level deeper in the halved range until range size becomes 0 or 1. So stack usage is proportional to log n.
Common Pitfall: If someone sees two recursive calls in code, they might think O(2^n). But note here only one of the binarySearch calls is executed after the comparison – either the left half or right half, not both. So it's a single recursive path, not branching. That makes it linear recursion (just that each step drops n dramatically). The pattern is divide-and-conquer with one subproblem, giving logarithmic complexity.
Comparison: The iterative binary search is also O(log n). The recursion doesn’t change complexity, just an alternate implementation.
Mistake: Some might think checking the middle is O(n) (if they confuse with scanning) but it’s O(1). The power of binary search is that elimination of half the data in each step.
We’ll delve more into divide-and-conquer recurrences (like binary search, merge sort, etc.) in the next section. Here we included binary search as a recursion example of logarithmic time.
Example 18: Naive Fibonacci (Exponential Recursion)
// Problem: Compute nth Fibonacci number (naively)
function fib(n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
What it Does: Computes Fibonacci numbers by definition: fib(0)=0, fib(1)=1, fib(n)=fib(n-1)+fib(n-2). This is a classic example of an exponential-time recursive algorithm.
Time Complexity: O(2^n) (exponential). Specifically, the recurrence is T(n) = T(n-1) + T(n-2) + O(1). This solves to about O(φ^n) where φ≈1.618 (the golden ratio), which is often loosely described as O(2^n) (Analyzing Time and Space Complexity in Recursive Algorithms). The intuition: the recursion tree branches out roughly doubling the number of calls for each increment of n. For example, to compute fib(5), it will compute a call tree with fib(4) and fib(3), and fib(4) will call fib(3) and fib(2), etc. The number of calls grows exponentially.
To see the pattern:
fib(0) or fib(1) = 1 call.
fib(2) calls fib(1) and fib(0) (2 calls) plus current -> ~3 calls.
fib(3) calls fib(2) and fib(1) -> fib(2) further calls -> ~5 calls.
fib(4) -> ~9 calls.
fib(5) -> ~15 calls. This is 2^n - 1 for fib(n+1) actually. Generally ~O(2^n) (How to find time complexity of an algorithm? | Adrian Mejia Blog). Growth is exponential.
(How to find time complexity of an algorithm? | Adrian Mejia Blog) (How to find time complexity of an algorithm? | Adrian Mejia Blog) shows that fib recursion yields about 2^n calls (specifically fib(4) had 9 calls, fib(5) 15 calls, which is 2^4+1 and 2^5-1 pattern). So it indeed grows exponentially.
Space Complexity: O(n) – The deepest recursive call chain happens when we keep subtracting 1 (following the leftmost branch fib(n-1) until n=0). That depth is n, so O(n) stack space.
Common Pitfall: Many learners initially think this is O(n) or O(n²). It’s much worse. The overlapping subproblem structure (each fib(n-2) overlaps with part of fib(n-1)'s computation) causes a combinatorial explosion of calls. It’s a famous example where naive recursion is terribly inefficient.
Common Mistake: Believing each level halves n so it might be log n – not in this case! Here each call spawns two calls on significantly smaller subproblems. The problem size decreases by 1 or 2, but branch factor is 2, making it exponential. (Divide-and-conquer with one subcall gave log n; with two roughly equal subcalls, we get exponential when we can’t reuse results.)
Optimization: This is where memoization or DP comes in. If we memoize fib, we get O(n) time because each fib(k) is computed once. But without memo, it recomputes the same subfib values many times.
We’ll revisit this in the DP section. For now, raw recursion fib is a cautionary tale: two recursive calls that overlap leads to 2^n time.
Example 19: Euclidean GCD (Logarithmic but not obvious)
// Problem: Compute GCD (greatest common divisor) of a and b using Euclid's algorithm
function gcd(a, b) {
if (b === 0) return a;
return gcd(b, a % b);
}
What it Does: This uses the property gcd(a, b) = gcd(b, a mod b). It repeatedly takes remainders.
Time Complexity: O(log(min(a,b))) on average (and in the worst-case, O(log a + log b), which is roughly O(log max(a,b))). Euclid’s algorithm runs in time proportional to the number of digits of the numbers (or number of steps of mod operation). In the worst case (when numbers are consecutive Fibonacci numbers), it takes the most steps. It turns out the number of recursive calls is bounded by about 5 * number of decimal digits (or a constant times bits) of the smaller number. This is logarithmic in the numeric value ([PDF] Backtracking). For simplicity, we say O(log n) if we consider a and b of size ~n.
To illustrate: gcd(48, 18) -> gcd(18, 48%18=12) -> gcd(12, 18%12=6) -> gcd(6, 12%6=0) -> done. That was 4 calls. In general, each step reduces the numbers significantly (at least one gets smaller considerably).
Space Complexity: O(log n) (stack depth equals number of recursive calls, which is log-scale in the size of numbers).
Note: This is a more advanced analysis case because input is numeric values not length of a data structure. If we measure input size in terms of bits (say input has k-bit numbers), the complexity is O(k). But if we treat the numbers themselves as n and m, complexity is O(log(min(n,m))).
For our purposes, realize gcd recursion is pretty efficient – sublinear in the value of inputs.
Common Mistake: Thinking it’s O(n) because it’s recursive like factorial. But here n is not the number of recursive steps typically. The mod operation can skip many numbers in one go. The worst-case scenario is when remainders don't drop super-fast (which happens for Fibonacci-like pairs), but still, the count of steps relates to Fibonacci index ~ log φ (since Fibonacci numbers grow exponentially with index). So it’s logarithmic.
Summary of Basic Recursion Patterns: Linear recursion (like factorial, list processing) is O(n). Branching recursion can explode: e.g. fib ~O(2^n). But sometimes recursion divides the problem making it much faster (binary search O(log n), gcd ~O(log n)). The key is to set up the recurrence T(n) and solve or reason it out.
One powerful technique to analyze recursive algorithms is the recursion tree method – visualizing the recursion as a tree of subproblems and summing the work. We’ll use that explicitly in the next section for more complex recurrences (like divide-and-conquer and branching cases) to build intuition.
Before that, a quick note on space in recursion: Always consider that each recursive call adds to the call stack. If a recursion is tail-recursive (like factorial here, though we multiply after returning, not tail call in JS sense but conceptually linear), the space is linear. If recursion splits, the space is still at most the depth of the deepest branch at any time (other branches are separate call paths, not simultaneous unless multi-threaded). For fib, one branch goes deep then returns, then the other – so the max stack depth is n (if always taking the n-1 branch first). For divide & conquer, depth often ~log n.
Now, let’s formally use recursion trees to handle patterns like divide-and-conquer recurrences and others, which often yield complexities like O(n log n).
Recursion Trees and Divide-and-Conquer Analysis
When recursion splits into multiple subcalls, especially of substantial size, it helps to draw a recursion tree to sum up the total work. The idea is to visualize each recursive call as a node in a tree, with children for each recursive subcall. Then you can sum the work done at each level of the tree and figure out the total.
Divide-and-Conquer algorithms break a problem into smaller subproblems, solve each recursively, and combine results. They often have recurrences of the form T(n) = a * T(n/b) + f(n), where:
a = number of subproblems,
n/b = size of each subproblem (assuming equal splitting for simplicity),
f(n) = cost of dividing and combining (outside recursion).
The Master Theorem provides solutions for many such recurrences, but here we focus on intuition via recursion trees.
Recursion Tree Method:
Identify the recurrence: how many subcalls and their sizes, plus the non-recursive work per call.
Draw a tree: root node = size n problem, it spawns children for each recursive call (with their input sizes).
Label each node (or each level) with the cost of the work done at that call (excluding recursive call costs).
Sum costs across each level of the tree.
Determine how many levels the recursion goes (depth).
Sum the costs of all levels.
Common patterns and results:
T(n) = T(n-1) + O(1): recursion tree is just a chain of n nodes with constant work each -> total O(n).
T(n) = 2T(n/2) + O(1): like binary recursion with trivial combine (e.g. count nodes in a binary tree). Each level doubles the number of nodes but work per node is O(1). Number of levels ~ log₂ n (until subproblem size 1). Each level has ~2^k calls of size ~n/2^k. Each call does O(1). Level 0: 1 call cost O(1); Level 1: 2 calls cost 2O(1); ... Level log n: ~2^{log n} = n calls cost nO(1). Actually, in this case, the sum of all levels forms a series 1 + 2 + 4 + ... + n ≈ 2n - 1 = O(n). So T(n) = O(n). (This models things like traversing all nodes of a binary tree or summing an array by splitting halves.)
T(n) = 2T(n/2) + O(n): this is merge sort. At each level, the merging cost O(n) per problem. At level 0: cost n. Level 1: two subproblems of size n/2, each merge cost O(n/2) so total level cost ~ n. Level 2: four subproblems of size n/4 each, total cost 4 * (n/4) = n. So each level costs ~n (algorithm - Why is merge sort worst case run time O (n log n)? - Stack Overflow). Number of levels ~ log₂ n (until subproblem size 1). So total = cost per level * number of levels ≈ n * (log₂ n + 1) = O(n log n) (algorithm - Why is merge sort worst case run time O (n log n)? - Stack Overflow). This tree has levels where the number of nodes doubles but work per node halves, balancing out to equal work per level (Mastering the Merge Sort: The Power of Efficient Sorting - Medium) (Analysis of merge sort (article) - Khan Academy).
T(n) = T(n-1) + T(n-2) + O(1): Fibonacci recursion. The recursion tree is almost a full binary tree. The number of leaves ~ F(n) (fib number) ~ φ^n (exponential). The largest cost is in the leaf count. You can show levels have exponential growth roughly until depth n. Total ~ O(2^n). [We already reasoned this in the fib example.]
T(n) = T(n/2) + T(2n/3) + O(n): an uneven split example (like some divide step that splits into one part size ~n/2 and another ~2n/3). The tree is not balanced, but the longest path defines depth, and summing costs is trickier. But one can still sum level costs by considering how many nodes of each size. (We might skip detailed math here, but generally such recurrences often yield O(n log n) or similar if splits are not too skewed.)
Let’s do some concrete examples using recursion trees:
Example 20: Merge Sort Recurrence (O(n log n))
Merge sort recursively divides the array in half, sorts each half, then merges. The recurrence:
a = 2 subproblems,
size = n/2 each,
f(n) = O(n) to merge the two sorted halves.
Recurrence: T(n) = 2 T(n/2) + O(n).
Recursion Tree:
Level 0: 1 problem of size n, cost = cn (for some constant c times n for the merge step).
Level 1: 2 problems of size n/2, each costs c(n/2). Total = 2 * c*(n/2) = cn.
Level 2: 4 problems of size n/4, each cost c(n/4). Total = 4 * c*(n/4) = cn.
...
Level k: 2^k problems of size n/2^k, each cost c(n/2^k). Total = 2^k * c*(n/2^k) = c*n.
This continues until the subproblem size becomes 1 (base case). How many levels? Solve n/2^k = 1 => 2^k = n => k = log₂ n. So there are log₂ n levels (plus maybe a constant number for base level).
Each level costs cn (except maybe the last level where each of n elements is individually a sorted list, merging cost could be considered 0 at leaves). Summing: (log₂ n + 1) levels \ cn per level = cn(log₂ n + 1). Drop constants: *O(n log n)(algorithm - Why is merge sort worst case run time O (n log n)? - Stack Overflow).
So merge sort is O(n log n) (Merge Sort Algorithm - Java, C, and Python Implementation | DigitalOcean). This matches known results: doubling the input size increases runtime by a factor n log n pattern, which is significantly better than n² of simpler sorts for large n.
(algorithm - Why is merge sort worst case run time O (n log n)? - Stack Overflow) (algorithm - Why is merge sort worst case run time O (n log n)? - Stack Overflow) illustrate this analysis: each level has ≤6N operations (for some constant factor 6 in that explanation), and there are log N levels, yielding O(n log n).
Example 21: Binary Tree Traversal (O(n)) via Recursion Tree
Consider a function that counts nodes in a binary tree:
function countNodes(root) {
if (!root) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
Recurrence: T(n) = T(n_left) + T(n_right) + O(1). In the worst case of a balanced tree, n_left ≈ n/2, n_right ≈ n/2 (ignoring one for odd). So roughly T(n) = 2T(n/2) + O(1).
We actually know intuitively this visits each node exactly once. Complexity = O(n).
Recursion Tree reasoning: At root: cost O(1) to count the node itself. It spawns two calls for left and right subtrees of size ~n/2 each. So level 0 cost ~1 (constant). Level 1: two nodes (the roots of each subtree) each counted with O(1) -> total 2. Level 2: 4 nodes counted -> 4. ... Level log n: ~n/1 nodes (the leaves) each count O(1) -> n. Sum = 1 + 2 + 4 + ... + n ≈ 2n - 1 = O(n). The merge cost here is trivial (just adding up counts, effectively constant per node). Thus, O(n).
This is consistent with the idea that traversing each node once is linear. The recursion tree approach shows that although there are many calls, they correspond one-to-one with nodes in the tree (no node is processed more than once, no repeated subproblem). Contrast with Fibonacci, where subproblems overlap – recursion tree had many more leaves than n.
Key insight: If the recursion subdivides the problem into disjoint subsets (like separate halves or separate subtrees), total work is often linear with respect to total input (n) if combine cost isn’t too high, because you are effectively just processing each element in those subproblems exactly once across the tree. If recursion reuses subproblems or overlaps them (like fib), that’s when complexity explodes unless you use memoization.
Example 22: Quicksort (Average O(n log n), Worst O(n²))
Quicksort picks a pivot, partitions array into elements less than pivot and greater than pivot, then recurses on those parts.
Average case: The pivot splits roughly in half on average (not exactly half, but let's assume equal for simplicity). Recurrence average: T(n) = T(n/2) + T(n/2) + O(n) for partitioning (the partition cost is linear). This is same as merge sort recurrence: O(n log n) average.
Worst case: If pivot is always worst (e.g., largest element), one side gets n-1 elements, the other gets 0. Recurrence: T(n) = T(n-1) + T(0) + O(n). Simplify: T(n) = T(n-1) + O(n). This recurrence solves to O(n²). (It’s basically 1 + 2 + ... + n in partition cost across recursion depth n.)
Recursion Tree (average): Similar to merge sort: each level does O(n) partitioning total, depth ~ log n, total O(n log n).Recursion Tree (worst-case): Level 0: cost n (partition), level 1: cost n-1 (next partition) etc, summing n + (n-1) + ... + 1 ≈ n(n+1)/2 = O(n²).
Quicksort’s average is n log n, but one must be aware of worst-case n². Usually random pivot selection or median-of-three is used to mitigate worst-case chances.
Important Lesson: Some recurrences like quicksort can have different outcomes depending on input distribution. Big O typically refers to worst-case unless specified average-case.
Common Pitfall: Thinking quicksort is always n log n or forgetting the worst-case scenario. In interviews, noting that naive quicksort is worst-case n² but expected n log n is important.
Example 23: Exponential Recursion Tree (Fibonacci)
We already did Fibonacci but let’s formally treat it with a recursion tree:
For fib(n):
root: cost O(1) (maybe just the addition).
it calls fib(n-1) and fib(n-2). So level 1 has 2 calls (n-1 and n-2).
Those calls branch too. The tree roughly forms a binary tree but not full balanced; however, it has roughly 2^n leaves (exactly F(n+1) leaves if analyzing).
If n is large, the number of nodes in this recursion tree is ~2^n. More concretely, the sum of calls = fib(n+2) - 1 (one can prove by induction). That is exponential in n (Fib grows ~φ^n).
Recursion tree summation: It's not as straightforward to sum level by level because here the cost doesn’t nicely equalize. But we can see the number of nodes in the tree itself is exponential. Each call has constant work aside from subcalls. Thus total work ~ number of nodes ~ exponential.
One observation: In fib recursion tree, the number of leaves is fib(n) which ~φ^n / √5 (exponential), and leaves dominate the count. The work per level actually grows as levels deepen, unlike divide-and-conquer where it shrank or stayed equal.
Recap of Recursion Tree Patterns:
If subproblems cover distinct parts of the input, the total work is usually linearithmic or linear (like merge sort or traversal) not exponential.
If subproblems overlap or you have multiple calls that together process more than the total unique input (like recomputing same values), you can get exponential – unless optimized by caching.
Tips for Using Recursion Trees:
Sum of geometric series: if each level cost multiplies or divides by a constant, use formulae. E.g., cost per level constant => multiply by number of levels.
If tree is unbalanced, consider the longest branch as depth and try to bound total work by something like a series.
The Master Theorem is a quicker way for standard forms: e.g. T(n) = a T(n/b) + f(n):
If f(n) is smaller order than n^(log_b(a)), recursion cost dominates.
If f(n) is about equal to n^(log_b(a)), result is O(n^(log_b(a)) * log n).
If f(n) is larger, result is often O(f(n)). (But I digress; since this is a guide, intuition is enough.)
Now, let's use this understanding on some divide-and-conquer and recursive problem examples:
Example 24: Fast Exponentiation (Divide & Conquer, O(log n))
// Problem: Compute x^n (power) efficiently
function power(x, n) {
if (n === 0) return 1;
if (n % 2 === 0) {
let half = power(x, n/2);
return half * half;
} else {
return x * power(x, n - 1);
}
}
What it Does: Uses the trick that x^n = (x^(n/2))^2 for even n, and x^n = x * x^(n-1) for odd n.
Time Complexity: O(log n) – The recursion essentially halves n in each even step. In worst case, if n is odd it does one extra multiplication and reduces to an even, then halves. Roughly, for n of size say 13: it does one step to 12 (odd case), then halves repeatedly: 12 -> 6 -> 3 -> (odd) 2 -> 1. The number of calls is on the order of log₂ n (plus a couple for odd adjustments). For big n, the halving dominates, so complexity is proportional to the number of bits in n (log₂ n).
Recurrence: T(n) = T(n/2) + O(1) in even case, and T(n) = T(n-1) + O(1) in odd case. But an odd case immediately goes to an even case next call (n-1 is even). If you write out in worst-case scenario: T(n) <= T(n/2) + T(n-1) + O(1). That’s not typical form; easier is to see each bit of the binary representation of n results in at most one recursive call. So if n has k bits (around log₂ n = k), we have at most k calls.
Space Complexity: O(log n) – recursion depth about log n.
Recursion Tree: For simplicity, assume n is a power of 2 (so always even until base):
Level 0: exponent n.
Level 1: exponent n/2.
Level 2: exponent n/4.
...
Level k: exponent 1. Levels = log₂ n. Each level does constant work (multiplying results). Total = O(log n). If n is not a power of 2, an odd step adds one extra call but doesn’t add a level beyond maybe one more.
Compare: Computing x^n by naive multiplication xx...*x (n times) is O(n). This method is much faster for large n.
Common Mistake: Sometimes people forget this optimization and assume power must be O(n). Recognizing this divide-and-conquer pattern is key for algorithmic efficiency (it’s essentially exponentiation by squaring).
Example 25: Matrix Multiplication Naive vs Strassen (Advanced D&C)
Naive matrix multiply two n×n matrices: triple nested loop O(n³). But can be viewed as recurrence: we can form 8 sub-matrices multiplications of size n/2 (divide matrices into quadrants, the standard formula uses 8 multiplies of n/2 size matrices + combine). That recurrence: T(n) = 8 T(n/2) + O(n²) (for adding sub-results). Using Master Theorem: n^(log₂ 8) = n^3, f(n) = n² which is smaller order (n² vs n^3). So T(n) = Θ(n^3). (No improvement because it matches the obvious.)
Strassen’s algorithm reduces multiplications to 7 subproblems of size n/2 (at cost of more additions). Recurrence: T(n) = 7 T(n/2) + O(n^2). Here n^(log₂ 7) = n^~2.807..., and f(n)=n² is larger order? Actually, n^2 vs n^2.807: f(n) is lower order than n^2.807, so cost dominated by recursion. Solution: T(n) = Θ(n^2.807). It's better than n^3, though with a high constant and memory overhead.
We mention this to show how adjusting the “a” in the recurrence affects complexity: fewer subcalls yields better complexity if combine cost isn’t worse.
For everyday programming, Strassen is a niche; standard matrix multiply is fine until very large matrices.
Now that we’ve covered divide-and-conquer and recursion analysis, let’s move to dynamic programming, which is essentially recursion plus caching of overlapping subproblems. We already saw how naive recursion for Fibonacci is terrible, but with memoization it becomes linear. Dynamic programming problems often have complexity equal to the number of distinct subproblem states times the cost to compute each state (which often leads to polynomial time rather than exponential).
But before DP, let’s explicitly address memoization vs tabulation – two ways to implement DP – and how to analyze their complexity and space.
Memoization and Tabulation: Dynamic Programming Optimization
Dynamic Programming (DP) is an optimized recursion that stores results of subproblems to avoid recomputation. There are two main approaches:
Memoization (Top-Down): Start with the original problem, recursively solve subproblems, and cache their results. (Basically recursion + a lookup table.)
Tabulation (Bottom-Up): Build a table iteratively from smaller subproblems up to the original problem.
Both achieve the same number of subproblem computations; they differ in order of computation and space usage.
Mental Model: Identify the subproblem structure (state variables that define a subproblem, e.g., indices, remaining capacity, etc.). The number of unique subproblem states often determines DP complexity, because each state will be computed once. The transitions or recurrence give the work per state.
Complexity pattern in DP: Time Complexity ≈ (# of states) * (# of transitions per state) (Running time - Dynamic programming algorithm - Stack Overflow). The transitions per state is often constant or depends on some parameter (e.g., checking a few adjacent states). If each state loops over something, multiply that in.
Memoization vs Tabulation:
Time Complexity: Usually the same. Memoization might have a tiny overhead for recursion and hashing keys (if using a dictionary), but asymptotically they both compute each state once, so O(total states + total transitions) (Time Complexity comparision of memoized recursion and table method in Dynamic programming - Stack Overflow). So if a DP has, say, 100 subproblem states, each solved in constant time, overall O(100) which is O(1) if we consider input size large? But typically states are polynomial in input size.
Space Complexity:
Memoization uses recursion stack (which can be depth = number of states in worst cases) and a cache. Tabulation uses an array/table of states. Usually, memoization has higher space because of the recursion call stack in addition to the cache (Memoization Vs Tabulation). Tabulation often can be done in-place or with an array.
Memoization stack depth = longest dependency chain (could be n in worst-case). Table size = number of states. If caching in a dictionary, space = number of states.
Memo vs Tab difference: Tabulation sometimes allows you to reduce space by reusing space for states that are no longer needed (if you only depend on recent ones). Memoization by default stores all states computed (unless you intentionally free some).
Example: Fibonacci with memo vs tab:
States: fib(0)...fib(n) (n+1 states).
Transitions: fib(k) = fib(k-1)+fib(k-2) (constant time).
So complexity ~ O(n) time, O(n) space.
Memoization uses recursion depth n, plus a memo dictionary of size n.
Tabulation uses an array of size n and no recursion.
Recurrence to DP: Many recursive solutions (especially exponential ones) become polynomial with DP:
Fibonacci: O(n) with DP vs O(2^n) naive.
Backtracking with overlapping subsolutions (like DFS on graphs with cycles) becomes manageable with memo (turning exponential DFS into polynomial).
Key: DP avoids redundant work.
Let’s go through structured DP examples:
Dynamic Programming: Step-by-Step Patterns and Problems
Dynamic Programming usually involves breaking problems into subproblems with optimal substructure and overlapping subproblems. We’ll cover patterns like:
Fibonacci / Climbing Stairs (1D DP)
Coin Change / Unbounded Knapsack (1D DP with target)
0/1 Knapsack (2D DP)
Longest Common Subsequence (2D DP)
Edit Distance (2D DP)
Memoized DFS for Graphs or Trees (like caching results of subtrees or states)
DP with Sliding Window optimization or two-pointer optimization (though those are more like pattern optimizations).
Palindromic substrings or Partitioning (DP)
etc.
We will present a set of DP problems, explain the states and transitions, and derive complexity.
But first, a quick note on identifying DP patterns:
Look for a problem that can be broken into subproblems that reuse each other’s results.
If a naive recursion would recompute a lot, that’s a hint DP can cut it down.
Typical identifiable patterns:
Fibonacci-like (straight linear dependency) -> O(n).
Grid or matrix DP (like unique paths in grid or dynamic table filling) -> O(n*m).
Subset sum / Knapsack (double nested states like capacity vs items) -> O(n*W) etc.
Sequence alignment or edit distance (two indices) -> O(n*m).
DP on trees/graphs (cache results for subtrees or states of node + info).
DP with bit masks (e.g., traveling salesman with subsets) -> O(2^n * n), which is exponential in n but feasible for small n because state count is 2^n.
The complexity of a DP is often either polynomial (n^2, n^3, etc.) or at worst pseudopolynomial (depending on a numeric parameter like target sum), but well below brute force which might be exponential combinatorial.
Alright, let's tackle some DP examples:
Example 26: Fibonacci with Memoization (Top-Down DP)
We already discussed naive fibonacci. Now with memo:
let memo = {};
function fibMemo(n) {
if (n <= 1) return n;
if (n in memo) return memo[n];
memo[n] = fibMemo(n-1) + fibMemo(n-2);
return memo[n];
}
Time Complexity: O(n) – Each Fibonacci number from 0 up to n is computed once and stored (Running time - Dynamic programming algorithm - Stack Overflow). The recursion will fill the memo from base up. The number of recursive calls is 2n-1 or similar (each fib(k) for k<=n is computed once, and each returns immediately when called again from cache). So linear time. This is a dramatic improvement from O(2^n).
Space Complexity: O(n) – The memo stores n+1 numbers. The recursion stack depth is O(n) as well (it will recursively go down to fib(1) then bubble up, though tail recursion doesn’t apply here because it branches – but due to memo, branching after first run just returns). So both memory for memo and stack are O(n).
Common Pitfall: Without memo, it was exponential. With memo, time complexity equals number of states (n) because each state fib(k) solves in O(1) given its two already-computed children. This pattern (linear DP for linear recurrence) is fundamental.
Problem Variation: Climbing Stairs – “How many ways to climb n stairs if you can take 1 or 2 steps at a time?” It is essentially Fibonacci. DP or recursion with memo yields O(n). For completeness, one might present that as a separate problem but it’s identical in analysis.
We can provide that as an example code too:
// Climbing stairs (DP bottom-up)
function climbStairs(n) {
if (n <= 2) return n;
let ways = [0, 1, 2];
for (let i = 3; i <= n; i++) {
ways[i] = ways[i-1] + ways[i-2];
}
return ways[n];
}
Time: O(n), Space: O(n) (but can optimize to O(1) space by keeping just last two values).
Common mistake might be to attempt brute force recursion (exponential) for climbing stairs, but DP is straightforward.
Example 27: Coin Change (Count Ways) – 1D DP
Problem: Given coin denominations and an amount, find number of ways to make that amount (unlimited coins). This is a classic unbounded knapSack / coin change count problem.
DP Approach: Let ways[t] = number of ways to make sum t. Base: ways[0] = 1 (one way to make 0, use no coins). For each coin, we update ways.
Order matters: If counting combinations (order-insensitive), iterate coins outer, sum inner.
function countWaysToMakeAmount(coins, amount) {
let ways = Array(amount+1).fill(0);
ways[0] = 1;
for (let coin of coins) {
for (let x = coin; x <= amount; x++) {
ways[x] += ways[x - coin];
}
}
return ways[amount];
}
Time Complexity: O(n * amount) – n = number of coin types. The nested loops: outer n, inner up to amount. So if amount = M, complexity O(n * M). This is pseudo-polynomial (depends on numeric amount, not just coin count). But if M is considered input size (like value maybe large but given in unary length?), anyway for moderate amounts it’s fine.
If coins length is small, complexity is linear in amount. If amount is large, algorithm scales linearly in amount which might be an issue if amount is extremely large (like 1000000 or more, but still okay for many cases).
Space Complexity: O(M) for the ways array.
Explanation: We are essentially performing a DP table fill. Each state is an amount from 0 to M. Each coin yields a transition: ways[x] += ways[x-coin]. We compute each state once per coin. So state count * transitions = (M) * (n) = O(nM).
Common Mistake: If one tries a naive recursive solution “for each coin either use it or not” with recursion, that can blow up exponentially because of permutations. DP constrains counting by building up systematically.
Another Mistake: Confusing combination count vs permutation count. The above code counts combinations (order of coin usage doesn’t create new way). If we did outer loop for amount, inner for coin, we’d count permutations (which would be larger count, and algorithm would over-count). That’s a logical bug affecting correctness but not the complexity class (though an incorrect double count might appear to inflate operations similarly, but complexity remains nested loops either way).
Identifying pattern: This is like unbounded knapsack (each coin can be used multiple times). Complexity is product of amount and number of coin types (which is often fine since coin types are typically small and amount moderate).
Example 28: 0/1 Knapsack (DP)
Problem: Given items with values and weights, and a weight capacity W, find max value you can carry without exceeding W. n = number of items.
DP Approach: A classic 2D DP: dp[i][w] = max value achievable using first i items and capacity w. Recurrence: either take item i or not:
dp[i][w] = dp[i-1][w] // not take item i
if (weight[i] <= w):
dp[i][w] = max(dp[i][w], value[i] + dp[i-1][w - weight[i]]);
We fill table for i from 1..n, w from 0..W.
Code:
function knapsack(weights, values, W) {
let n = weights.length;
// (n+1) x (W+1) table initialized to 0
let dp = Array.from({length: n+1}, () => Array(W+1).fill(0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= W; w++) {
dp[i][w] = dp[i-1][w]; // not taking item i
if (weights[i-1] <= w) {
dp[i][w] = Math.max(dp[i][w], values[i-1] + dp[i-1][w - weights[i-1]]);
}
}
}
return dp[n][W];
}
(Note: using i indexed from 1 for convenience, with item index offset by 1.)
Time Complexity: O(n * W) – We have n+1 rows and W+1 columns, nested loop (Running time - Dynamic programming algorithm - Stack Overflow). If W is large, this is pseudo-polynomial (since input size in bits for W is log W). But if W is manageable (like thousands), it’s fine. For exact complexity, treat it as O(nW).
Space Complexity: O(n * W) for the DP table. We can optimize to O(W) if we only keep one row (when using rolling array, careful to iterate W backwards for 0/1 case). But using a full table is clear.
Insight: Without DP, trying all combinations of items (2^n possibilities) is exponential. DP reduces it to polynomial by exploiting substructure.
Common Mistake: Using recursion to try including/excluding each item leads to O(2^n) time (for large W, that's worse). The DP ensures we compute each state (i,w) once.
Pitfall: If W (capacity) is extremely large (like millions) and n large, O(nW) may be too slow. There are more advanced pseudo-poly algorithms or approximations in such cases, but that’s beyond scope.
Pattern recognition: Two variables (item index and remaining capacity) define state -> 2D table DP.
Example 29: Longest Common Subsequence (LCS) – 2D DP
Problem: Given two strings (length m and n), find length of longest common subsequence.
DP: Let dp[i][j] = LCS length of string1[0..i-1] and string2[0..j-1]. Recurrence:
If characters match:
dp[i][j] = 1 + dp[i-1][j-1].If not match:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Base row/col with 0 length.
Code:
function LCS_length(s1, s2) {
let m = s1.length, n = s2.length;
let dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i-1] === s2[j-1]) {
dp[i][j] = 1 + dp[i-1][j-1];
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
Time Complexity: O(m * n) – Nested loops over each index pair (Running time - Dynamic programming algorithm - Stack Overflow). Each cell does O(1) comparison and assignment. For two strings of lengths m and n, that's O(mn).
Space: O(m * n) for table. (Can be optimized to O(min(m,n)) if needed by storing only two rows at a time since current only depends on previous row and itself.)
Example: If s1 and s2 are each 1000 length, dp table = 1001 x 1001 ~ 1e6 cells, which is fine.
Common Mistake: Trying a brute force recursion (which tries all subsequences of one string and checks against other, exponential 2^m * maybe check cost) – extremely slow. DP cuts it down to polynomial.
Pitfall: Some may confuse with substring (contiguous) which would be different problem. Subsequence DP is as above. Substring longest common substring uses a slightly different DP (match -> 1 + diagonal, no carry from mismatch except reset).
Pattern: Two sequences -> typically O(m*n) DP.
Example 30: Edit Distance (Dynamic Programming)
Problem: Compute minimum edit distance (Levenshtein distance) between two strings (allowed operations: insert, delete, replace with cost 1 each).
DP: Let dp[i][j] = minimum edit distance between s1[0..i-1] and s2[0..j-1]. Recurrence: If last chars equal: dp[i][j] = dp[i-1][j-1]. If not equal:
dp[i][j] = 1 + min(
dp[i-1][j], // delete char from s1
dp[i][j-1], // insert char into s1 (or delete from s2)
dp[i-1][j-1] // replace char
)
Base: dp[0][j] = j (j inserts), dp[i][0] = i (i deletes).
Code:
function editDistance(s1, s2) {
let m = s1.length, n = s2.length;
let dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
for (let i = 0; i <= m; i++) dp[i][0] = i;
for (let j = 0; j <= n; j++) dp[0][j] = j;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s1[i-1] === s2[j-1]) {
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
}
}
}
return dp[m][n];
}
Time Complexity: O(m * n) – Two nested loops again (Running time - Dynamic programming algorithm - Stack Overflow). If each string is length N, that’s O(N²). For, say, N=1000, 1e6 operations, quite fine.
Space Complexity: O(m * n) for full table (can also optimize to O(min(m,n)) with trick, but anyway).
Common Mistake: A naive recursive solution tries all possibilities (exponential). DP yields polynomial time.
Identifiable pattern: It’s similar in structure to LCS, just with a different recurrence including replace operation. Many string DP problems follow a similar 2D table approach.
Example 31: Matrix Chain Multiplication (DP with optimal grouping)
(This one is a classic DP with O(n³) time, but just briefly.)
Problem: Given dimensions of matrices, find optimal parenthesization to multiply with minimal operations. For n matrices, there's a known DP solution in O(n³).
DP: dp[i][j] = minimum cost to multiply matrices i...j. We try every possible split k between i and j:
dp[i][j] = min_{i<=k<j} (dp[i][k] + dp[k+1][j] + cost to multiply two resulting matrices)
cost to multiply results = dimensions[i...k] * [k+1...j] multiplications.
Time Complexity: O(n³) – triple nested: i,j,k loops. For ~30 matrices, 27k operations, fine; for 100 matrices, 1e6 operations, fine. But grows quickly, so rarely beyond a few hundred.
Space: O(n²) table.
We won't code fully, but note the pattern: 3 nested loops, which is polynomial (cubic).
Common Mistake: Trying all binary tree structures of multiplication (which is Catalan number count ~ exponential) without DP is impossible for moderate n. DP prunes to polynomial.
This shows not all DP are just quadratic; some are cubic or higher, but still far better than exponential.
Example 32: DFS with Memo on Graph (Cutting Exponential to Polynomial)
Consider a directed acyclic graph (DAG) and a problem: count paths from node A to node B. A naive DFS would explore exponentially many paths if the graph is large. But if we memoize the result (count of paths from a node to B), we compute each node’s result once.
Time Complexity with memo: O(V + E) – essentially linear in graph size, because each node’s outgoing edges are processed once when computing its path count (algorithm - Why is the complexity of BFS O(V+E) instead of O(V*E)? - Stack Overflow).
Space: O(V) for memo + recursion stack (which is O(V) in worst-case depth).
For example:
function countPaths(u, target, graph, memo = {}) {
if (u === target) return 1;
if (u in memo) return memo[u];
let total = 0;
for (let v of graph[u]) {
total += countPaths(v, target, graph, memo);
}
memo[u] = total;
return total;
}
If the graph has cycles, this would need cycle detection (and if cycle in path count, infinite paths if cycle reachable, or you'd break cycles). For DAG it’s fine.
Without memo, that DFS might revisit nodes many times => exponential blow-up for graphs with fan-out. With memo, it’s linear.
Key Pattern: This is essentially a DP on a directed acyclic graph (topologically, path counts). Many problems (like unique paths in grid can be seen as DAG DP, or counting arrangements) use DFS + memo as a technique.
Common Mistake: Not memoizing results in DFS on DAG: you end up exploring same subgraph repeatedly. E.g., in a binary tree, number of unique BST structures is Catalan, etc., but if you treat that as a graph of subproblems you can memo.
We’ve covered many patterns:
Straight loops (O(n), O(log n)).
Nested loops (O(n²), etc.).
Recursion linear vs branching (O(n) vs O(2^n)).
Divide and conquer (O(n log n) sorts, O(log n) binary search).
Dynamic Programming (various polynomial complexities).
Graph traversals (O(V+E) with DFS/BFS, exponential if naive but manageable with DP for counts, etc.).
Finally, let’s address specialized patterns like sliding window and two pointers, which often allow converting an O(n²) nested loop problem into O(n) by maintaining a window or pair of pointers. We touched on this in the iterative section (Example 7 and later we will do more in depth).
Sliding Window and Two-Pointer Techniques: Optimizing Loops
Sliding Window: This technique solves problems involving subarrays or substrings of contiguous elements. Instead of using a nested loop to examine every possible subarray (O(n²)), a sliding window moves start and end indices through the array/string while maintaining some condition, often achieving O(n).
Two-Pointers: A generalized form where two indices move through the data structure (not necessarily maintaining a contiguous window, sometimes one from start, one from end). Common for sorted arrays (two-sum), or fast-slow pointer in linked lists, etc. Typically results in O(n) or O(n log n) solutions for problems that naive would be higher.
Mental Model: For many problems, an outer loop and an inner loop can be replaced by a single loop that adjusts two pointers. The inner loop's work is distributed across the outer loop iterations, making total linear. Essentially, each element is visited a constant number of times by pointers, turning O(n*n) into O(n) (Sliding Window Algorithm Explained | Built In).
Identifying patterns:
"Find subarray/substring that satisfies X" (like sum <= K, or contains certain elements, etc.) often -> sliding window.
"Find pair/triplet in sorted array with certain property" -> two pointers from ends.
"Partition array by condition" -> two pointers.
"Remove duplicates in-place" -> slow/fast pointers.
"Cycle detection in linked list" -> fast/slow pointer.
Tips:
Sliding window works when increasing the window makes condition worse and decreasing makes it better, or vice versa, so you can adjust boundaries to maintain or restore condition.
Usually requires arrays or strings (something indexable).
For two-pointer on sorted arrays, you can increment one pointer or decrement the other based on sum comparisons.
We will go through some examples:
Example 33: Maximum Sum Subarray of Fixed Length (Sliding Window)
Problem: Given an array and an integer k, find the maximum sum of any contiguous subarray of length k.
Naive: Compute sum of every length-k subarray with a loop for each start (O(n*k)). If k ~ n, that’s O(n²).
Sliding Window: Use a window of length k, slide it by 1 each time by subtracting the element leaving and adding the new element entering.
function maxSumSubarray(arr, k) {
let n = arr.length;
if (k > n) return null;
// compute sum of first k elements
let sum = 0;
for (let i = 0; i < k; i++) sum += arr[i];
let maxSum = sum;
for (let i = k; i < n; i++) {
sum += arr[i] - arr[i-k]; // slide window forward by 1
if (sum > maxSum) maxSum = sum;
}
return maxSum;
}
Time Complexity: O(n) – We do one initial O(k) summation and then n-k steps of O(1) work each. Overall O(n + k) which is O(n) for large n (Sliding Window Algorithm Explained | Built In).
Space Complexity: O(1).
Comment: Classic example where nested approach (outer loop for start index, inner loop summing k elements) would be O(n*k). Sliding window achieves O(n).
Common Mistake: Not realizing you can update the sum in constant time when moving the window. The pattern "add arr[i], remove arr[i-k]" is key.
This pattern is straightforward when subarray length is fixed.
Example 34: Longest Substring without Repeating Characters (Variable Sliding Window)
Problem: Find length of longest substring of a string that has all unique characters.
Naive: Check every substring for uniqueness (O(n²) substrings, checking each O(n) -> O(n³) worst-case).
Sliding Window: Expand the window until a repeat occurs, then contract from the left until the repeat is resolved, continue.
function lengthOfLongestUniqueSubstr(s) {
let seen = new Set();
let left = 0, maxLen = 0;
for (let right = 0; right < s.length; right++) {
while (seen.has(s[right])) {
// remove leftmost until the duplicate char is removed
seen.delete(s[left]);
left++;
}
seen.add(s[right]);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
Time Complexity: O(n) – Each character is added to the set once and removed at most once. The right pointer moves n steps. The left pointer also moves at most n steps (cumulatively). Thus the while loop overall doesn't iterate more than n times in total across the run (Backtracking And Time Complexity) (Sliding Window Algorithm Explained | Built In). So total operations ~2n = O(n).
Space: O(min(n, charset_size)), in worst case O(n) if all distinct.
Explanation: We maintain a window [left,right] with unique chars. If adding s[right] causes duplicate, we increment left (shrinking window) until it's unique again. The trick is that each character is processed (added or removed) at most once– making it linear.
Common Mistake: Thinking the inner while makes it O(n²). But observe, left only moves when a duplicate is found, and each time it moves it removes one char. No char gets removed more than once. So total iterations of the inner while across entire string ≤ n. This is a typical amortized analysis: inner loop doesn’t fully run for each outer index independently; it runs gradually over the length.
Alternate approach: Could also use an array index map to jump left directly to one past the previous occurrence of a duplicate char (that yields also O(n)). Either way complexity linear.
Example 35: Smallest Subarray with Sum ≥ S (Variable Window)
Problem: Given an array of positive integers and target S, find the length of smallest contiguous subarray with sum ≥ S. If none, return 0.
Approach: Use sliding window: expand right until sum ≥ S, then shrink left until sum < S, track the min length at each point.
function minSubArrayLen(nums, S) {
let n = nums.length;
let minLen = Infinity;
let sum = 0;
let left = 0;
for (let right = 0; right < n; right++) {
sum += nums[right];
while (sum >= S) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left];
left++;
}
}
return minLen === Infinity ? 0 : minLen;
}
Time Complexity: O(n) – Again, right moves n, left moves at most n, total ~2n steps in worst case (Backtracking And Time Complexity). Each element is added once and removed at most once. Thus linear.
Space: O(1).
Common Mistake: Using two nested loops: outer loop for start index, inner loop to find end index where sum >= S (that would be O(n²) in worst case if S only satisfied at end for each start). The window approach collapses that to linear by effectively reusing the work done.
Note: This works because all numbers are positive, so when sum ≥ S, moving left will only decrease sum, thus eventually making sum < S, at which point we need to move right again to increase it. This monotonic property ensures each pointer only moves forward.
If numbers could be negative, sliding window becomes trickier (because sum could increase or decrease unpredictably), and one might need different techniques (prefix sum + two-pointer if certain conditions, or algorithms like two-sum for sorted arrays, or more complex data structures).
Example 36: Two Sum (Two Pointers in Sorted Array)
Problem: Given a sorted array and a target, find two numbers that add up to target (return their indices or values).
Two-pointer Solution: Have one pointer l at start, another r at end. Compute sum = arr[l] + arr[r]. If sum < target, increment l (to increase sum). If sum > target, decrement r (to decrease sum). If equal, found the pair.
This is O(n). The sorting might have been O(n log n) if array wasn't sorted, but once sorted, finding the pair is linear.
function twoSumSorted(arr, target) {
let l = 0, r = arr.length - 1;
while (l < r) {
let sum = arr[l] + arr[r];
if (sum === target) {
return [l, r];
} else if (sum < target) {
l++;
} else {
r--;
}
}
return null;
}
Time Complexity: O(n) – each step moves one pointer inward, so at most n steps until l and r meet.
Space: O(1).
Common Mistake: Without sorting, two-sum is typically solved by a hash table in O(n) time (storing complements), or brute force O(n²). Sorting + two-pointer is O(n log n) for sort + O(n) for find = O(n log n) overall. If array already sorted, definitely use two-pointer.
Note: If asked just for existence or one pair, this is straightforward. If asked for all unique pairs that sum to target (like two-sum problem variant), you can similarly use two pointers but need to handle skipping duplicates – still O(n) for the scanning, output could be multiple pairs.
Example 37: Dutch National Flag (3-way partition, Two Pointers)
Problem: Given an array of 0s, 1s, and 2s, sort it in-place (partition into three groups).
Two-pointer approach: Use pointers low and high and an index i to traverse:
low tracks end of 0s section, high tracks start of 2s section from end.
Traverse i from 0 to high. If arr[i] = 0, swap with arr[low] and low++, i++. If arr[i] = 2, swap with arr[high] and high-- (don’t increment i in this case because the swapped value from end needs to be checked). If arr[i] = 1, i++.
This sorts in one pass O(n).
Time Complexity: O(n) – Each element is swapped at most once, and i traverses at most n steps.
Space: O(1).
This classic algorithm (DNF) is a two-pointer (actually three regions concept).
Common Mistake: Using counting sort approach (count 0,1,2 then overwrite array) – that’s also O(n) time but two-pointer is in-place one-pass which is elegant.
Example 38: Fast & Slow Pointer (Cycle Detection)
Problem: Detect if a linked list has a cycle.
Two-pointer approach: slow moves 1 step, fast moves 2 steps. If there is a cycle, fast will eventually meet slow (because fast laps slow). If list has length n and cycle length k, one can show they meet in O(n) steps. If no cycle, fast reaches end (null) and we conclude no cycle.
Time Complexity: O(n) – each iteration moves pointers, and they will either meet or hit null in linear time relative to length of list. Space: O(1).
Alternatively, using a hash set to record visited nodes is also O(n) but uses O(n) space. The two-pointer uses constant space.
Common Mistake: Not obvious maybe to come up with, but a classic pattern.
Why O(n): In worst case of cycle, they meet in at most n steps (some proofs skip but intuitive: each iteration, distance between slow and fast reduces by 1, so after at most cycle_length iterations they meet; cycle_length <= n).
We can keep going, but the trend is: sliding window and two-pointer techniques almost always result in linear time solutions by smartly reusing previous computations and avoiding nested loops.
Red flags that hint at using these techniques:
If the problem is about subarrays or substrings with certain conditions (sums, counts, unique characters, etc.), and all elements are positive or condition is monotonic – think sliding window.
If the problem involves sorted arrays or the need to find pairs/triplets that meet a condition (sum, difference) – think two pointers.
If an algorithm is about moving through a structure with different speeds (like finding middle of list or cycle detection) – think fast/slow pointers.
By mastering these, you can often reduce complexity from quadratic to linear. For instance, the built-in result said: “sliding window transforms two nested loops into one loop” (Sliding Window Algorithm Explained | Built In).
Let's reinforce with one more example:
Example 39: Trapping Rain Water (Two pointers from ends)
Problem: Given heights of bars, find total trapped rain water.
Naive: For each bar, scan left and right to find max height on both sides, water = min(max_left, max_right) - height (if positive). That’s O(n²).
Two-pointer solution: Use two pointers from ends, and keep track of leftMax and rightMax. At each step, move the lower side inward because that side determines water trapped.
function trapRainWater(height) {
let left = 0, right = height.length - 1;
let leftMax = 0, rightMax = 0;
let totalWater = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
totalWater += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
totalWater += rightMax - height[right];
}
right--;
}
}
return totalWater;
}
Time Complexity: O(n) – Each index is visited once from either left end or right end.
Space: O(1).
Why it works: It always moves the pointer at the side with smaller height. The intuition is that the water level on the shorter side is limited by that side, so you can compute water and move inward. If you move the taller side first, you might miss some water that could have been trapped had a smaller wall come from the short side.
Common Mistake: Not trivial to come up with if you haven't seen before. Many try some stacking or DP approach. But this two-pointer is neat and linear.
Red flag scenario: problems where naive involves checking both left and right for each position usually hint at two-pointer or precomputed arrays of max left and max right (which is also O(n) with two passes or O(n) with DP arrays). Two-pointer here is optimal.
Conclusion: Sliding window and two-pointer techniques are powerful for optimizing certain types of loop problems. They essentially ensure that the inner loop doesn’t re-do work from scratch for each outer iteration, instead it reuses the state of the previous iteration.
(Backtracking And Time Complexity) emphasizes that in many sliding window problems, the total work of the inner adjustments is limited relative to the outer loop (usually linear overall), making the algorithm linear.
Summary and Final Tips
We’ve explored a wide range of algorithmic complexity patterns, from basic loops to advanced DP and pointer techniques. Here’s a quick mapping of problem patterns to complexities:
Straight-line code or single loops: O(1) or O(n).
Nested loops (independent): Multiply complexities -> often O(n²), O(n³), etc.
Cascading loops (one after another): Add complexities -> O(n + m) etc., drop lower terms -> usually O(n).
Recursion (single branch): Number of calls = depth -> often O(n) or O(log n).
Recursion (multiple branches): If each call spawns b calls, can be exponential O(b^n) unless limited by smaller subproblem sizes. Balanced binary recursion without overlap (like tree traversal) yields O(n). Balanced with combine (like mergesort) yields O(n log n). Overlapping recursion (like naive DP problems) yields exponential but DP reduces it drastically.
Divide & Conquer: Use recursion trees or Master Theorem. Typical outcomes:
a subproblems of size 1/b each:
If f(n) (combine cost) is O(n^c) where c < log_b(a): complexity ~ O(n^{log_b(a)}) (subproblem cost dominates).
If c == log_b(a): complexity ~ O(n^c * log n).
If c > log_b(a): complexity ~ O(f(n)) (combine dominates).
e.g. merge sort: a=2, b=2, log_b(a)=1, f(n)=n = n^1, equal case -> O(n^1 * log n) = O(n log n). Quick sort avg similar. Binary search: a=1, b=2, log_2(1)=0, f(n)=O(1) = n^0, c=0 equals log_b(a)=0, so O(n^0 * log n)=O(log n).
Dynamic Programming: Usually polynomial. Count states and transitions. If state defined by say (i,j), that suggests O(n*m) typically. If by (i, some range) and you try splits, could be O(n³) (like matrix chain).
Graph Traversal: BFS/DFS is O(V+E) (algorithm - Why is the complexity of BFS O(V+E) instead of O(V*E)? - Stack Overflow) (linear in size of graph). Backtracking on graphs is exponential if it explores many possibilities, but often prune or DP can help.
Sliding Window/Two Pointers: Often turn O(n²) problems into O(n). The hallmark is that each element is processed a small constant number of times, instead of an inner loop fully for each outer step.
Space complexity considerations: Always factor in:
If using recursion, call stack adds space equal to depth.
If using DP table or arrays, space is number of states or elements stored.
In place algorithms try to keep space O(1).
Sometimes you trade space for time (e.g., use a hash set to achieve O(n) time at cost of O(n) space).
Final Red Flags & Best Practices:
If you see double nested loops over the same data structure, suspect O(n²). Ask: can this be optimized? Sometimes sorting + clever loop or using data structures can reduce it.
If you see recursive function that calls itself more than once, check if it’s overlapping subproblems (like Fibonacci). If yes, think about memoization to avoid exponential blow-up.
If you see a solution that tries all combinations or subsets, complexity likely 2^n or n! (very expensive). For moderate n (like n up to 20), 2^n might be borderline. For n=10, n! = 3.6M combos, maybe okay; n=11 -> 39M combos, borderline. Always consider constraints.
If input size is said to be large (like n=100,000 or more), an O(n²) solution will not finish in reasonable time. You should aim for O(n log n) or O(n).
Amortized analysis tip: Sometimes a piece of code has a nested loop, but due to how indices move, it’s amortized linear. E.g., the sliding window examples: though there's a while inside a for, overall it's linear. Explain that each element enters and leaves the window at most once. This kind of reasoning is crucial to argue down the complexity.
Accidental quadratic: be careful with operations inside loops that might be O(n) themselves. For example, concatenating strings in a loop (each concat could be O(n) making it O(n²) overall). Or using an array
splicein a loop (which is O(n) per splice). These hidden costs can creep in.Memory constraints: Sometimes an algorithm is fast enough in time but uses too much memory (e.g., a DP table for extremely large n might not fit). Then you find space optimizations (like only storing needed slices).
Parallel tasks: If an algorithm has independent parts, total is sum. E.g., processing two arrays separately is O(n)+O(m). But if it's the same n, that's O(n).
Big O Notation reminders:
Drop constants: O(2n) -> O(n), O(n + 1000) -> O(n).
Drop lower terms: O(n² + n) -> O(n²).
Use Big Theta (Θ) if you want to say more precisely about growth when applicable, but Big O is usually fine for upper bound.
Sometimes mention Best/Average/Worst if relevant (like quicksort or search in an unbalanced BST vs balanced BST).
Wrapping Up: The ability to determine complexity for any algorithm comes with practice:
Trace through loops to count operations.
Translate recursion to recurrence and solve or reason by tree.
Recognize common patterns (sorting, searching, DP, graph traversal).
Check edge cases: sometimes an algorithm performs differently on worst-case input vs average (like quicksort). State which complexity you refer to.
Always verify with small examples or bounds whether the complexity formula makes sense (e.g., test extreme case mentally: if n doubles, does the predicted complexity doubling (linear), quadrupling (quad), etc., align with logic?).
Finally, in an interview or practical setting:
Communicate assumptions: e.g., “Assuming list length is n, this loop is O(n). If this inner operation is O(1), overall O(n). If it's using a data structure operation that is O(log n), then it becomes O(n log n).” Clarify if needed.
Highlight bottlenecks: The highest order term tells you which part of code dominates runtime. Focus optimization efforts there.
Use examples: If unsure, simulate with small n to see pattern (like fib calls count).
With deep understanding, you can approach any algorithm, break it down, and determine its complexity with confidence – an essential skill for optimizing code and succeeding in technical interviews at big tech companies or in competitive programming. Always strive for intuitive reasoning: if something feels slow as n grows, quantify that feeling with Big O; if something is efficient, articulate why (each element processed once, etc.).
By practicing problems of each category we covered (loops, recursion, DP, graph, pointers), you will build a strong intuition to recognize the pattern and immediately recall the typical complexity. Soon, determining time and space complexity will become second nature in your algorithm design process.
