Divide and Conquer Strategy and Recurrence Relations in DSA Typescript

Mental Model

Break a big problem into smaller similar problems, solve each one, then combine results.

Analogy: Like cutting a big pizza into slices, eating each slice, then enjoying the whole pizza.

Big Problem
   ↓
[Divide]
 /     \
Smaller  Smaller
Problem  Problem
   ↓       ↓
[Solve] [Solve]
   ↓       ↓
[Combine Results]
   ↓
Final Answer

Dry Run Walkthrough

Input: Find the sum of array [2, 4, 6, 8] using divide and conquer

Goal: Calculate the total sum by splitting the array into halves, summing each half, then adding them

Step 1: Divide array [2,4,6,8] into two halves: [2,4] and [6,8]

[2,4,6,8] -> divided into [2,4] and [6,8]

Why: Splitting makes the problem smaller and easier to solve

Step 2: Divide [2,4] into [2] and [4]

[2,4] -> divided into [2] and [4]

Why: Keep dividing until subarrays have one element

Step 3: Sum single elements: sum([2])=2 and sum([4])=4

[2] sum=2, [4] sum=4

Why: Base case: single element sum is the element itself

Step 4: Combine sums of [2] and [4]: 2 + 4 = 6

sum([2,4])=6

Why: Combine results of smaller problems

Step 5: Divide [6,8] into [6] and [8]

[6,8] -> divided into [6] and [8]

Why: Divide second half similarly

Step 6: Sum single elements: sum([6])=6 and sum([8])=8

[6] sum=6, [8] sum=8

Why: Base case for second half

Step 7: Combine sums of [6] and [8]: 6 + 8 = 14

sum([6,8])=14

Why: Combine results of smaller problems

Step 8: Combine sums of [2,4] and [6,8]: 6 + 14 = 20

sum([2,4,6,8])=20

Why: Final combination gives total sum

Result:

sum([2,4,6,8])=20

Annotated Code

DSA Typescript

class DivideAndConquer {
  static sumArray(arr: number[], start: number, end: number): number {
    if (start > end) {
      return 0; // base case: empty range sum is 0
    }
    if (start === end) {
      return arr[start]; // base case: single element sum
    }
    const mid = Math.floor((start + end) / 2);
    const leftSum = this.sumArray(arr, start, mid); // sum left half
    const rightSum = this.sumArray(arr, mid + 1, end); // sum right half
    return leftSum + rightSum; // combine results
  }
}

const arr = [2, 4, 6, 8];
const totalSum = DivideAndConquer.sumArray(arr, 0, arr.length - 1);
console.log(`sum([${arr.join(",")}])=${totalSum}`);

if (start > end) { return 0; }

base case: empty range sum is 0

if (start === end) { return arr[start]; }

base case: return single element sum

const mid = Math.floor((start + end) / 2);

find middle index to divide array

const leftSum = this.sumArray(arr, start, mid);

recursively sum left half

const rightSum = this.sumArray(arr, mid + 1, end);

recursively sum right half

return leftSum + rightSum;

combine sums of halves

Output

sum([2,4,6,8])=20

Complexity Analysis

Time: O(n) because each element is visited once during the divide and combine steps

Space: O(log n) due to recursion stack depth from dividing array in halves

vs Alternative: Compared to simple loop summing in O(n) time and O(1) space, divide and conquer uses more space but illustrates recursive problem solving

Edge Cases

Empty array

Returns 0 immediately without recursion

DSA Typescript

if (start > end) { return 0; }

Single element array

Returns the element itself as sum

DSA Typescript

if (start === end) { return arr[start]; }

When to Use This Pattern

When a problem can be split into smaller similar problems and combined, use divide and conquer to simplify and solve efficiently.

Common Mistakes

Mistake: Not defining a proper base case causing infinite recursion
Fix: Add base case to return when subproblem size is one element

Mistake: Incorrect mid calculation causing wrong splits
Fix: Use Math.floor((start + end) / 2) to find middle index correctly

Summary

Breaks a problem into smaller parts, solves each, then combines results.

Use when a problem can be divided into similar subproblems.

The key is to define a base case and combine partial solutions correctly.