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

Recall & Review

beginner

What is the main idea behind the Divide and Conquer strategy?

Divide and Conquer breaks a problem into smaller parts, solves each part separately, and then combines the results to solve the original problem.

beginner

What does a recurrence relation describe in algorithms?

A recurrence relation expresses the running time of a recursive algorithm in terms of the running time of smaller inputs.

intermediate

Explain the recurrence relation for Merge Sort.

Merge Sort splits the array into two halves, sorts each half, and merges them. Its recurrence is T(n) = 2T(n/2) + O(n), where O(n) is the merging time.

intermediate

What is the Master Theorem used for?

The Master Theorem helps solve recurrence relations of divide and conquer algorithms to find their time complexity quickly.

beginner

Give an example of a problem solved by Divide and Conquer.

Sorting an array using Merge Sort or Quick Sort is a classic example of Divide and Conquer.

Which step is NOT part of the Divide and Conquer approach?

A Divide the problem into smaller subproblems

B Solve the subproblems independently

C Combine the solutions of subproblems

D Ignore the smaller subproblems and solve the big problem directly

Divide and Conquer always breaks the problem into smaller parts instead of ignoring them.

What does the recurrence T(n) = 2T(n/2) + n represent?

A Binary search time

B Linear search time

C Merge Sort time complexity

D Constant time operation

This recurrence describes Merge Sort, which divides the problem into two halves and merges in linear time.

Which theorem helps solve recurrences like T(n) = aT(n/b) + f(n)?

A Pythagorean Theorem

B Master Theorem

C Binomial Theorem

D Fundamental Theorem of Calculus

The Master Theorem is designed to solve divide and conquer recurrence relations.

In Divide and Conquer, what is the typical time complexity of combining solutions?

A Linear time

B Constant time

C Exponential time

D Logarithmic time

Combining solutions often takes linear time, like merging two sorted arrays.

Which of these is NOT a Divide and Conquer algorithm?

A Bubble Sort

B Merge Sort

C Binary Search

D Quick Sort

Bubble Sort is a simple sorting algorithm that does not use Divide and Conquer.

Describe the three main steps of the Divide and Conquer strategy with an example.

Think about how sorting an array can be done by splitting, sorting parts, and merging.

Explain how recurrence relations help analyze the time complexity of recursive algorithms.

Consider how the time for a problem depends on smaller problems.

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 process all elements sequentially

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 separately.

2. Step 2: Combine the solutions of subproblems

   After solving smaller parts, their results are combined 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 problem into smaller parts, solve, then combine [OK]

Common Mistakes:

• Confusing divide and conquer with brute force
• Thinking it processes elements sequentially only
• 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 divides array into two halves

   It splits the array into two parts, sorts each recursively.

2. Step 2: Merge step takes linear time O(n)

   After sorting halves, merging takes O(n) time.

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 as constant time
• Choosing wrong number of recursive calls

3. What is the output of the following C# code that uses a divide and conquer approach to sum an array?

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);
}

int[] nums = {2, 4, 6, 8};
Console.WriteLine(SumArray(nums, 0, nums.Length - 1));

medium

A. 20

B. 10

C. 0

D. Throws runtime error

Solution

1. Step 1: Understand the recursive sum function

   The function splits the array into halves until one element remains, then sums back up.

2. Step 2: Calculate sum of array elements

   Sum = 2 + 4 + 6 + 8 = 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Sum of {2,4,6,8} = 20 [OK]

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

Common Mistakes:

• Confusing mid calculation causing infinite recursion
• Forgetting base case when start == end
• Miscounting sum of elements

4. Identify the error in this C# code implementing a divide and conquer algorithm to find the maximum element:

int MaxElement(int[] arr, int start, int end) {
    if (start == end) return arr[start];
    int mid = (start + end) / 2;
    int leftMax = MaxElement(arr, start, mid);
    int rightMax = MaxElement(arr, mid, end);
    return Math.Max(leftMax, rightMax);
}

medium

A. The base case should check if start > end

B. Math.Max should be replaced with Math.Min

C. The second recursive call should be MaxElement(arr, mid + 1, end)

D. The mid calculation should be (start + end + 1) / 2

Solution

1. Step 1: Analyze recursive calls for correct subarray ranges

   The first call covers start to mid, so the second must cover mid+1 to end to avoid overlap.

2. Step 2: Identify the off-by-one error

   Using mid again in second call causes overlap and possible infinite recursion.

3. Final Answer:

   The second recursive call should be MaxElement(arr, mid + 1, end) -> Option C

4. Quick Check:

   Correct subarray split avoids overlap [OK]

Hint: Second half starts at mid+1, not mid [OK]

Common Mistakes:

• Using mid instead of mid+1 causing infinite recursion
• Changing base case incorrectly
• Replacing max with min mistakenly

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(\log n)

D. O(n)

Solution

1. Step 1: Identify parameters a, b, and f(n)

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

2. Step 2: Calculate log_b(a) and compare with f(n)

   log_3(3) = 1, so f(n) = n = n^{log_b(a)}.

3. Step 3: Apply Master Theorem case 2

   Since f(n) = Theta(n^{log_b(a)}), time complexity is O(n).

4. Final Answer:

   O(n) -> Option D

5. Quick Check:

   Master theorem case 2 = O(n) [OK]

Hint: Compare f(n) with 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