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.

Practice

1. What is the main idea behind the Divide and Conquer strategy in algorithms?

easy

A. Break the problem into smaller subproblems, solve them independently, then combine results

B. Solve the problem by trying all possible solutions one by one

C. Use a single loop to iterate through all elements

D. Store all intermediate results to avoid repeated calculations

Solution

1. Step 1: Understand the divide and conquer approach

   It splits a big problem into smaller parts that are easier to solve.

2. Step 2: Combine the solutions of smaller parts

   After solving subproblems, their results are merged to get the final answer.

3. Final Answer:

   Break the problem into smaller subproblems, solve them independently, then combine results -> Option A

4. Quick Check:

   Divide and conquer = split, solve, combine [OK]

Hint: Divide big problems into smaller parts, solve, then merge [OK]

Common Mistakes:

• Confusing divide and conquer with brute force
• Thinking it uses only loops without recursion
• Mixing it up with dynamic programming

2. Which of the following is the correct recurrence relation for the Merge Sort algorithm?

easy

A. T(n) = 3T(n/3) + O(n^2)

B. T(n) = 2T(n/2) + O(n)

C. T(n) = T(n/2) + O(1)

D. T(n) = T(n-1) + O(1)

Solution

1. Step 1: Recall Merge Sort process

   Merge Sort splits array into two halves, sorts each half, then merges.

2. Step 2: Write recurrence relation

   It calls itself twice on half size (2T(n/2)) plus merging cost O(n).

3. Final Answer:

   T(n) = 2T(n/2) + O(n) -> Option B

4. Quick Check:

   Merge Sort recurrence = 2T(n/2) + n [OK]

Hint: Merge sort splits in two, merges in linear time [OK]

Common Mistakes:

• Using T(n-1) instead of T(n/2)
• Confusing merge cost with recursive calls
• Choosing cubic or quadratic terms incorrectly

3. What is the output of the following TypeScript function that uses divide and conquer to find the maximum element?

function findMax(arr: number[], left: number, right: number): number {
  if (left === right) return arr[left];
  const mid = Math.floor((left + right) / 2);
  const maxLeft = findMax(arr, left, mid);
  const maxRight = findMax(arr, mid + 1, right);
  return maxLeft > maxRight ? maxLeft : maxRight;
}

const array = [3, 5, 1, 8, 2];
console.log(findMax(array, 0, array.length - 1));

medium

A. 3

B. 5

C. 8

D. 2

Solution

1. Step 1: Understand the function logic

   The function splits the array into halves recursively and compares max values.

2. Step 2: Trace the recursive calls on array [3,5,1,8,2]

   Max in left half [3,5,1] is 5; max in right half [8,2] is 8; final max is 8.

3. Final Answer:

   8 -> Option C

4. Quick Check:

   Max element found by divide and conquer = 8 [OK]

Hint: Divide array, find max in halves, pick bigger [OK]

Common Mistakes:

• Returning min instead of max
• Incorrect mid calculation causing infinite recursion
• Mixing indices causing wrong subarray

4. Identify the error in the following recurrence relation and fix it:

T(n) = 2T(n/2) + O(n^2)

This recurrence is supposed to represent the time complexity of a divide and conquer algorithm similar to Merge Sort.

medium

A. Change O(n^2) to O(n) because merging takes linear time

B. Change 2T(n/2) to T(n-1) because it is not dividing

C. Change O(n^2) to O(log n) because merging is logarithmic

D. No error, the recurrence is correct

Solution

1. Step 1: Analyze the merging cost in divide and conquer

   In Merge Sort-like algorithms, merging two halves takes O(n) time, not O(n^2).

2. Step 2: Correct the recurrence relation

   Replace O(n^2) with O(n) to reflect the linear merging cost.

3. Final Answer:

   Change O(n^2) to O(n) because merging takes linear time -> Option A

4. Quick Check:

   Merging cost = O(n), not O(n^2) [OK]

Hint: Merging in divide and conquer is linear, not quadratic [OK]

Common Mistakes:

• Assuming merging is quadratic
• Changing recursive calls incorrectly
• Ignoring the cost of merging step

5. Given the recurrence relation T(n) = 3T(n/3) + n, what is the time complexity of the algorithm using the Master Theorem?

hard

A. O(log n)

B. O(n^2)

C. O(n^{\log_3 3}) = O(n)

D. O(n log n)

Solution

1. Step 1: Identify parameters for Master Theorem

   Here, a=3, b=3, f(n)=n. Calculate log_b(a) = log_3(3) = 1.

2. Step 2: Compare f(n) with n^{log_b(a)}

   f(n) = n and n^{log_b(a)} = n^1 = n, so f(n) = Theta(n^{log_b(a)}).

3. Step 3: Apply Master Theorem case 2

   When f(n) = Theta(n^{log_b(a)}), T(n) = Theta(n^{log_b(a)} log n) = Theta(n log n).

4. Final Answer:

   O(n log n) -> Option D

5. Quick Check:

   Master Theorem case 2 gives O(n log n) [OK]

Hint: Use Master Theorem: compare f(n) with n^{log_b(a)} [OK]

Common Mistakes:

• Ignoring the log factor in case 2
• Confusing log base or parameters a and b
• Choosing linear time incorrectly