Divide and Conquer Strategy and Recurrence Relations in DSA Javascript

Mental Model

Divide a big problem into smaller parts, solve each part, then combine results to get the answer.

Analogy: Like cutting a big pizza into slices, eating each slice one by one, then feeling full from the whole pizza.

Big Problem
   ↓ Divide
[Small Part 1] [Small Part 2] ... [Small Part n]
   ↓ Solve each
[Answer 1] [Answer 2] ... [Answer n]
   ↓ Combine
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 smaller parts, summing each, then adding results

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

[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] and [4]

Why: Keep dividing until parts are simple enough to solve directly

Step 3: Sum [2] = 2 and [4] = 4, then combine to get 6

6

Why: Base case sums are direct values, combine to get partial sum

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

[6] and [8]

Why: Divide second half similarly to simplify

Step 5: Sum [6] = 6 and [8] = 8, then combine to get 14

14

Why: Sum base parts and combine for partial sum

Step 6: Combine partial sums 6 and 14 to get total sum 20

20

Why: Final step combines all partial results for answer

Result:

20

Annotated Code

DSA Javascript

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

const array = [2, 4, 6, 8];
const totalSum = DivideAndConquer.sumArray(array, 0, array.length - 1);
console.log(totalSum);

if (start > end) { return 0; }

handle empty segment base case

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

return single element as base case sum

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

find middle index to split array

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

recursively sum left half

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

recursively sum right half

return leftSum + rightSum;

combine partial sums for total

Output

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 the array in half each time

vs Alternative: Compared to a simple loop summing elements in O(n) time and O(1) space, divide and conquer uses more space but can be parallelized

Edge Cases

Empty array

Function should handle gracefully, returning 0 or no sum

DSA Javascript

Added explicit guard: if (start > end) { return 0; }

Single element array

Returns the single element as sum immediately

DSA Javascript

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

When to Use This Pattern

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

Common Mistakes

Mistake: Not defining a base case causing infinite recursion
Fix: Add a base case that returns when the problem is smallest (e.g., one element)

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

Summary

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

Use it when a problem can be divided into similar subproblems.

The key is to solve small parts easily and combine for the full answer.

Practice

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

easy

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

B. Use a single loop to iterate through all elements

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

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 C

4. Quick Check:

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

Hint: Divide and conquer means split, solve, then merge results [OK]

Common Mistakes:

• Confusing divide and conquer with brute force
• Thinking it uses only one loop
• Mixing it with dynamic programming

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

easy

A. T(n) = 3T(n/3) + O(log n)

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

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

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

Solution

1. Step 1: Recall Merge Sort recurrence

   Merge Sort splits array into two halves, sorts each half, then merges in O(n).

2. Step 2: Write recurrence form

   It calls itself twice on half size (2T(n/2)) plus linear merge time 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)
• Adding O(n^2) instead of O(n)
• Confusing with Quick Sort recurrence

3. What is the output of the following JavaScript function that uses divide and conquer?

function sumArray(arr) {
  if (arr.length === 1) return arr[0];
  const mid = Math.floor(arr.length / 2);
  return sumArray(arr.slice(0, mid)) + sumArray(arr.slice(mid));
}
console.log(sumArray([2, 4, 6, 8]));

medium

A. 20

B. 24

C. 10

D. Error

Solution

1. Step 1: Understand the function behavior

   The function splits the array into halves recursively and sums elements.

2. Step 2: Trace the calls for [2,4,6,8]

   Split into [2,4] and [6,8], sumArray([2,4]) = 6, sumArray([6,8]) = 14, total 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Sum of 2+4+6+8 = 20 [OK]

Hint: Divide array, sum halves, add results [OK]

Common Mistakes:

• Confusing slice indices causing wrong sums
• Assuming function returns array instead of sum
• Forgetting base case for single element

4. Identify the error in this divide and conquer function to find the maximum element:

function findMax(arr) {
  if (arr.length === 1) return arr[0];
  const mid = Math.floor(arr.length / 2);
  const leftMax = findMax(arr.slice(0, mid));
  const rightMax = findMax(arr.slice(mid));
  return leftMax > rightMax ? leftMax : rightMax;
}
console.log(findMax([]));

medium

A. Fails on empty array input causing infinite recursion

B. Incorrect comparison operator used

C. No error, works correctly

D. Slices do not split array properly

Solution

1. Step 1: Check base case for empty array

   The function does not handle empty array input, so arr.length === 0 is not checked.

2. Step 2: Understand recursion on empty array

   Calling findMax([]) leads to infinite recursion because base case is only for length 1.

3. Final Answer:

   Fails on empty array input causing infinite recursion -> Option A

4. Quick Check:

   Empty input needs base case to avoid infinite calls [OK]

Hint: Always check for empty input base case [OK]

Common Mistakes:

• Ignoring empty array edge case
• Assuming slice always returns non-empty array
• Thinking comparison operator is wrong

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

hard

A. O(log n)

B. O(n^2)

C. 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 n).

4. Final Answer:

   O(n log n) -> Option D

5. Quick Check:

   Master Theorem case 2 = n log n [OK]

Hint: Compare f(n) to n^log_b(a) for Master Theorem [OK]

Common Mistakes:

• Confusing log base or parameters a and b
• Choosing wrong Master Theorem case
• Ignoring the extra n term in recurrence