Divide and Conquer Strategy and Recurrence Relations in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Divide and Conquer strategy in algorithms?

Divide and Conquer is a method where a problem is split into smaller subproblems, each solved independently, and then combined to form the final solution.

intermediate

Explain the role of recurrence relations in Divide and Conquer algorithms.

Recurrence relations express the running time of Divide and Conquer algorithms by relating the time for a problem of size n to the time for smaller subproblems.

intermediate

What is the Master Theorem used for?

The Master Theorem provides a way to solve recurrence relations of Divide and Conquer algorithms to find their time complexity quickly.

intermediate

Given the recurrence T(n) = 2T(n/2) + n, what is the time complexity using Divide and Conquer?

The time complexity is O(n log n), because the problem divides into two halves and combines results in linear time.

beginner

Why is Divide and Conquer efficient for sorting algorithms like Merge Sort?

Because it breaks the array into smaller parts, sorts them independently, and merges them efficiently, reducing the overall time compared to simple sorting algorithms.

What is the first step in the Divide and Conquer approach?

A Combine the solutions

B Divide the problem into smaller subproblems

C Solve the problem directly

D Ignore the problem

Divide and Conquer starts by dividing the problem into smaller parts.

Which recurrence relation represents the Merge Sort algorithm?

A T(n) = 2T(n/2) + n

B T(n) = T(n-1) + 1

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

D T(n) = n^2

Merge Sort divides the array into two halves and merges in linear time, so T(n) = 2T(n/2) + n.

What does the 'conquer' step in Divide and Conquer mean?

A Splitting the problem

B Ignoring subproblems

C Solving the smaller subproblems

D Combining the results

The conquer step solves each smaller subproblem independently.

Which of these is NOT a characteristic of Divide and Conquer algorithms?

A Solve the problem iteratively without recursion

B Solve subproblems recursively

C Combine solutions

D Divide the problem

Divide and Conquer typically uses recursion, not purely iterative methods.

What does the Master Theorem help with?

A Sorting arrays

B Writing code faster

C Debugging algorithms

D Solving recurrence relations

The Master Theorem helps solve recurrence relations to find time complexity.

Describe the three main steps of the Divide and Conquer strategy and give a simple example.

Think about how you would split a big task into smaller tasks, solve them, and then put the answers together.

Explain how recurrence relations represent the time complexity of Divide and Conquer algorithms and how the Master Theorem is used.

Focus on how the time for a big problem depends on smaller problems and how to solve that relation.

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