Divide and Conquer Strategy and Recurrence Relations in DSA Java - 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 get the final solution.

beginner

Explain the three main steps of Divide and Conquer.

1. Divide: Split the problem into smaller parts.
2. Conquer: Solve each smaller part recursively.
3. Combine: Merge the solutions of the parts to solve the original problem.

intermediate

What is a recurrence relation in the context of Divide and Conquer?

A recurrence relation expresses the total time of an algorithm in terms of the time taken by smaller subproblems plus the time to combine their results.

intermediate

Given the recurrence T(n) = 2T(n/2) + n, what does each term represent?

2T(n/2): Time to solve two subproblems of size n/2 each.
n: Time to combine the solutions of the subproblems.

intermediate

How does the Master Theorem help with recurrence relations?

The Master Theorem provides a direct way to find the time complexity of divide and conquer recurrences without solving them step-by-step.

Which of the following best describes the 'Conquer' step in Divide and Conquer?

A Splitting the problem into smaller parts

B Ignoring the smaller problems

C Combining the solutions of subproblems

D Solving the smaller subproblems recursively

The 'Conquer' step means solving each smaller subproblem, usually by recursion.

What does the recurrence T(n) = 3T(n/3) + n represent in Divide and Conquer?

A Three subproblems of size n/3 and linear combine time

B Two subproblems of size n/2 and constant combine time

C One subproblem of size n and quadratic combine time

D No subproblems, just linear time

It shows three subproblems each of size n/3 and a combine step taking linear time n.

Which step is NOT part of Divide and Conquer?

A Conquer

B Iterate

C Combine

D Divide

'Iterate' is not a standard step in Divide and Conquer.

What is the purpose of solving a recurrence relation in algorithms?

A To find the time complexity of recursive algorithms

B To find the space used by the algorithm

C To count the number of variables

D To debug the code

Recurrence relations help find the time complexity of recursive algorithms.

Using the Master Theorem, what is the time complexity of T(n) = 2T(n/2) + n?

A O(log n)

B O(n^2)

C O(n log n)

D O(n)

This recurrence solves to O(n log n) using the Master Theorem.

Describe the Divide and Conquer strategy and its three main steps.

Think about how you solve a big problem by breaking it into smaller ones.

Explain what a recurrence relation is and how it relates to Divide and Conquer algorithms.

Consider how the total time depends on smaller parts and combining.

Practice

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

easy

A. Store all intermediate results to avoid repeated calculations

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

C. Use a single loop to iterate through all elements

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

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 subproblems

   After solving smaller parts, 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 D

4. Quick Check:

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

Hint: Divide big problem 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) = T(n/2) + O(1)

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

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

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

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)
• Ignoring the merge cost O(n)
• Confusing with quicksort recurrence

3. What is the output of the following Java method that uses divide and conquer?

public static int sumArray(int[] arr, int start, int end) {
    if (start == end) return arr[start];
    int mid = (start + end) / 2;
    return sumArray(arr, start, mid) + sumArray(arr, mid + 1, end);
}

public static void main(String[] args) {
    int[] nums = {2, 4, 6, 8};
    System.out.println(sumArray(nums, 0, nums.length - 1));
}

medium

A. 20

B. 10

C. 0

D. Compilation error

Solution

1. Step 1: Understand the method's logic

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

2. Step 2: Calculate sum of array elements

   Sum of {2,4,6,8} = 2+4+6+8 = 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Sum of array = 20 [OK]

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

Common Mistakes:

• Confusing mid calculation causing infinite recursion
• Forgetting to include last element
• Assuming method returns partial sums

4. Identify the error in the following recurrence relation code snippet for a divide and conquer algorithm:

int divideConquer(int n) {
    if (n == 1) return 1;
    int result = divideConquer(n / 2) + divideConquer(n / 2);
    return result + n;
}

medium

A. The base case should be n == 0 instead of n == 1

B. No error, code is correct

C. The function calls divideConquer(n / 2) twice causing redundant work

D. The addition of n should be outside the return statement

Solution

1. Step 1: Analyze recursive calls

   The function calls divideConquer(n/2) twice separately, repeating work.

2. Step 2: Identify redundancy

   Calling the same function twice with same argument duplicates effort, inefficient.

3. Final Answer:

   The function calls divideConquer(n / 2) twice causing redundant work -> Option C

4. Quick Check:

   Repeated calls with same input cause redundancy [OK]

Hint: Avoid duplicate recursive calls with same parameters [OK]

Common Mistakes:

• Thinking base case is wrong
• Ignoring duplicate calls
• Assuming addition placement causes error

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

hard

A. O(n log n)

B. O(n^2)

C. O(n)

D. O(log n)

Solution

1. Step 1: Identify parameters for Master Theorem

   Here, a=3, b=3, f(n)=n.

2. Step 2: Calculate log_b(a)

   log_3(3) = 1.

3. Step 3: 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)}).

4. Step 4: Apply Master Theorem case 2

   Time complexity T(n) = Theta(n log n).

5. Final Answer:

   O(n log n) -> Option A

6. Quick Check:

   Master theorem case 2 = n log n [OK]

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

Common Mistakes:

• Confusing log base or value
• Choosing wrong Master theorem case
• Ignoring the additive term n