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

Consider the following C code snippet that counts the number of recursive calls made by merge sort on an array of size n = 4. What is the printed output?

DSA C

int count = 0;

void merge_sort(int arr[], int left, int right) {
    count++;
    if (left < right) {
        int mid = (left + right) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
    }
}

int main() {
    int arr[4] = {4, 3, 2, 1};
    merge_sort(arr, 0, 3);
    printf("%d\n", count);
    return 0;
}

A 7

B 8

C 6

D 5

💡 Hint

Count how many times merge_sort is called including the initial call.

The merge_sort function is called once for the whole array, then recursively for each half. For n=4, calls are: merge_sort(0,3), merge_sort(0,1), merge_sort(2,3), merge_sort(0,0), merge_sort(1,1), merge_sort(2,2), merge_sort(3,3). Total 7 calls.

🧠 Conceptual

intermediate

Master Theorem Case Identification

Given the recurrence relation T(n) = 3T(n/4) + n, which case of the Master Theorem applies to find the time complexity?

A None of the above

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

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

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

💡 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. Since f(n) = n = n^1, and 1 > 0.792, f(n) grows faster than n^log_b(a). But since f(n) is polynomially larger, Case 3 applies only if f(n) dominates by a polynomial factor. Here, f(n) = n, which is larger, so Case 3 applies. However, since f(n) = n and n^log_b(a) ≈ n^0.792, f(n) dominates, so Case 3 applies.

❓ Predict Output

advanced

Output of Recursive Function with Divide and Conquer

What is the output of the following C function when called with mystery(8)?

DSA C

int mystery(int n) {
    if (n <= 1) return 1;
    return mystery(n / 2) + mystery(n / 2);
}

int main() {
    printf("%d\n", mystery(8));
    return 0;
}

A 8

B 4

C 16

D 1

💡 Hint

Trace the calls and sum the return values.

mystery(8) calls mystery(4) twice, each mystery(4) calls mystery(2) twice, and so on until base case mystery(1) returns 1. Total calls double each level, resulting in 8.

🔧 Debug

advanced

Identify the Error in Recurrence Relation Implementation

The following C code attempts to compute T(n) = 2T(n/2) + n using recursion and print the result for n=8. What error will occur when running this code?

DSA C

int T(int n) {
    if (n == 1) return 1;
    return 2 * T(n / 2) + n;
}

int main() {
    printf("%d\n", T(8));
    return 0;
}

A Runtime error due to infinite recursion

B No error, output is 32

C Compilation error due to missing return type

D Wrong output: 20 instead of 24

💡 Hint

Check base case and recursive calls carefully.

The code correctly implements the recurrence with base case n=1 returning 1. For n=8, T(8) = 2*T(4)+8, T(4)=2*T(2)+4, T(2)=2*T(1)+2=2*1+2=4, so T(4)=2*4+4=12, T(8)=2*12+8=32. The output is 32, and there is no error.

🧠 Conceptual

expert

Time Complexity of Strassen's Matrix Multiplication

Strassen's algorithm multiplies two n x n matrices using 7 recursive multiplications of size n/2 plus some additions. Which recurrence relation best describes its time complexity?

A T(n) = 8T(n/2) + O(n^2)

B T(n) = 8T(n/2) + O(n^3)

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

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

💡 Hint

Strassen reduces multiplications from 8 to 7, additions cost O(n^2).

Strassen's algorithm uses 7 recursive multiplications on n/2 matrices plus O(n^2) additions and subtractions, so recurrence is T(n) = 7T(n/2) + O(n^2).