Divide and Conquer Strategy and Recurrence Relations in DSA C# - Build from Scratch

Divide and Conquer Strategy and Recurrence Relations

📖 Scenario: You are helping a small bakery organize its daily sales data. The bakery wants to find the highest sale amount quickly using a method called divide and conquer. This method breaks the problem into smaller parts, solves each part, and then combines the answers.

🎯 Goal: Build a C# program that uses the divide and conquer strategy to find the maximum sale amount from a list of daily sales. You will also understand how the problem breaks down into smaller parts and how the total work adds up using recurrence relations.

📋 What You'll Learn

Create an array called sales with exact values: 120, 450, 300, 700, 150, 600

Create an integer variable called n that stores the length of the sales array

Write a recursive function called FindMaxSale that takes the array sales, a start index start, and an end index end

Use divide and conquer inside FindMaxSale to find the maximum sale between start and end

Print the maximum sale amount found by calling FindMaxSale with the full array range

💡 Why This Matters

🌍 Real World

Divide and conquer is used in many real-world problems like sorting large datasets, searching efficiently, and solving complex problems by breaking them into smaller parts.

💼 Career

Understanding divide and conquer and recurrence relations is important for software developers and engineers to write efficient algorithms and optimize performance.

1

Create the sales data array

Create an integer array called sales with these exact values: 120, 450, 300, 700, 150, 600.

DSA C#

// Create the sales array with given values
// Your code here

Hint

Use int[] sales = { ... }; to create the array with the exact numbers.

2

Create the length variable

Create an integer variable called n that stores the length of the sales array.

DSA C#

int[] sales = {120, 450, 300, 700, 150, 600};
// Create an integer variable n to store the length of sales
// Your code here

Hint

Use sales.Length to get the number of elements in the array.

3

Write the recursive FindMaxSale function

Write a recursive function called FindMaxSale that takes the array sales, a start index start, and an end index end. Use divide and conquer to find the maximum sale between start and end. If start equals end, return the sale at that index. Otherwise, split the range into two halves, find the maximum in each half by calling FindMaxSale recursively, and return the larger of the two.

DSA C#

int[] sales = {120, 450, 300, 700, 150, 600};
int n = sales.Length;

// Write the recursive FindMaxSale function below
// Your code here

Hint

Use recursion to split the array into halves until one element remains, then compare and return the maximum.

4

Print the maximum sale amount

Print the maximum sale amount by calling FindMaxSale with the sales array, start as 0, and end as n - 1.

DSA C#

int[] sales = {120, 450, 300, 700, 150, 600};
int n = sales.Length;

int FindMaxSale(int[] sales, int start, int end)
{
    if (start == end)
    {
        return sales[start];
    }
    int mid = (start + end) / 2;
    int leftMax = FindMaxSale(sales, start, mid);
    int rightMax = FindMaxSale(sales, mid + 1, end);
    return leftMax > rightMax ? leftMax : rightMax;
}

// Print the maximum sale amount below
// Your code here

Hint

Call FindMaxSale(sales, 0, n - 1) and print the result using Console.WriteLine.

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