Divide and Conquer Strategy and Recurrence Relations in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Merge Sort Call Count

What is the output of the following C# code that counts the number of recursive calls in a merge sort?

DSA C#

using System;

class Program {
    static int callCount = 0;

    static void MergeSort(int[] arr, int left, int right) {
        callCount++;
        if (left >= right) return;
        int mid = (left + right) / 2;
        MergeSort(arr, left, mid);
        MergeSort(arr, mid + 1, right);
    }

    static void Main() {
        int[] array = {5, 3, 8, 6};
        MergeSort(array, 0, array.Length - 1);
        Console.WriteLine(callCount);
    }
}

A 6

B 8

C 7

D 5

💡 Hint

Count how many times the MergeSort function is called including the initial call and all recursive calls.

The merge sort splits the array recursively until single elements remain. For an array of size 4, the calls are:

• Call 1: full array (0-3)
• Call 2: left half (0-1)
• Call 3: left half of left half (0-0)
• Call 4: right half of left half (1-1)
• Call 5: right half (2-3)
• Call 6: left half of right half (2-2)
• Call 7: right half of right half (3-3)

Total calls = 7.

🧠 Conceptual

intermediate

Recurrence Relation for Binary Search

What is the correct recurrence relation for the time complexity of binary search on an array of size n?

A T(n) = T(n-1) + O(1)

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

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

D T(n) = T(n/2) + O(1)

💡 Hint

Binary search divides the problem size by half each step and does constant work per step.

Binary search splits the array in half each time and does a constant amount of work to compare the middle element. So the recurrence is T(n) = T(n/2) + O(1).

🔧 Debug

advanced

Identify the Error in the Recurrence Calculation

What error does the following C# code produce when trying to calculate the recurrence T(n) = 2T(n/2) + n for n=8?

DSA C#

using System;

class Program {
    static int Recurrence(int n) {
        if (n == 1) return 1;
        return 2 * Recurrence(n / 2) + n;
    }

    static void Main() {
        Console.WriteLine(Recurrence(8));
    }
}

A Output: 24

B StackOverflowException

C Output: 15

D Compile-time error

💡 Hint

Trace the recursive calls and sum the results carefully.

The recurrence expands as:

• T(8) = 2*T(4) + 8
• T(4) = 2*T(2) + 4
• T(2) = 2*T(1) + 2
• T(1) = 1

Calculating bottom-up:

• T(1) = 1
• T(2) = 2*1 + 2 = 4
• T(4) = 2*4 + 4 = 12
• T(8) = 2*12 + 8 = 32

But the code returns 24 because integer division truncates and the base case is at n==1, so the calls are correct and output is 24.

❓ Predict Output

advanced

Output of QuickSort Partition Calls

What is the output of the following C# code that counts the number of partition calls in a quicksort implementation on the array {4, 2, 7, 1}?

DSA C#

using System;

class Program {
    static int partitionCalls = 0;

    static int Partition(int[] arr, int low, int high) {
        partitionCalls++;
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp1 = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp1;
        return i + 1;
    }

    static void QuickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = Partition(arr, low, high);
            QuickSort(arr, low, pi - 1);
            QuickSort(arr, pi + 1, high);
        }
    }

    static void Main() {
        int[] array = {4, 2, 7, 1};
        QuickSort(array, 0, array.Length - 1);
        Console.WriteLine(partitionCalls);
    }
}

A 3

B 2

C 5

D 4

💡 Hint

Count how many times Partition is called during the quicksort process.

Partition is called once for the full array (0-3), then for the left subarray (0-1), and then for the right subarray (3-3) which does not call partition because low is not less than high. So total calls = 3.

🧠 Conceptual

expert

Master Theorem Case Identification

Given the recurrence T(n) = 3T(n/4) + n log n, which case of the Master Theorem applies to determine the asymptotic complexity?

A Case 1: f(n) = O(n^log_b(a) - ε), so T(n) = Θ(n^log_b(a))

B Case 2: f(n) = Θ(n^log_b(a) * log^k(n)), so T(n) = Θ(n^log_b(a) * log^{k+1}(n))

C Case 3: f(n) = Ω(n^log_b(a) + ε), so T(n) = Θ(f(n))

D None of the Master Theorem cases apply

💡 Hint

Calculate log base b of a and compare f(n) with n^log_b(a).

Here, a=3, b=4, so log_b(a) = log_4(3) ≈ 0.792. The function f(n) = n log n = Θ(n^{1} * log n). Since 1 > 0.792, f(n) grows faster than n^{log_b(a)} but not polynomially larger. This fits Case 2 of the Master Theorem where f(n) = Θ(n^{log_b(a)} * log^k n) with k=1.

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