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

Practice

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

easy

A. Use a single loop to solve the problem iteratively

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

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

D. Store all intermediate results to avoid repeated calculations

Solution

1. Step 1: Understand Divide and Conquer approach

   It splits a big problem into smaller parts that are easier to solve.

2. Step 2: Combine 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 C

4. Quick Check:

   Divide and Conquer = Break, Solve, Combine [OK]

Hint: Divide big problem into parts, solve parts, then combine [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 on an array of size n?

easy

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

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

C. T(n) = T(n/2) + 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 recursively, then merges in O(n) time.

2. Step 2: Write recurrence relation

   It calls itself twice on size n/2 plus linear merge step, so T(n) = 2T(n/2) + O(n).

3. Final Answer:

   T(n) = 2T(n/2) + O(n) -> Option B

4. Quick Check:

   Merge Sort recurrence = 2 halves + merge O(n) [OK]

Hint: Two halves plus linear merge step means 2T(n/2)+n [OK]

Common Mistakes:

• Using T(n-1) instead of T(n/2)
• Ignoring the merge step cost
• Confusing with quicksort recurrence

3. Consider the following C code implementing a divide and conquer function:

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

What is the time complexity T(n) of this function?

medium

A. O(n^2)

B. O(n)

C. O(log n)

D. O(n log n)

Solution

1. Step 1: Identify recurrence relation

   The function calls itself twice on n/2 plus does O(n) work, so T(n) = 2T(n/2) + n.

2. Step 2: Solve recurrence using Master Theorem

   For T(n) = 2T(n/2) + n, the solution is O(n log n).

3. Final Answer:

   O(n log n) -> Option D

4. Quick Check:

   2 calls on half + linear work = n log n [OK]

Hint: Two halves plus linear work means n log n time [OK]

Common Mistakes:

• Thinking it is O(n) by ignoring recursive calls
• Confusing with O(log n) for single call
• Mistaking it for quadratic O(n^2)

4. The following recurrence relation is given:

T(n) = 3T(n/3) + n^2

There is a mistake in the code implementing this recurrence. Which fix will correct the recurrence to match the intended divide and conquer approach?

medium

A. Change the recursive calls to 3T(n/3) and keep n^2 as extra work

B. Change the extra work from n^2 to n log n

C. Change the recursive calls to T(n-1) and keep n^2

D. Change the recursive calls to 2T(n/2) and keep n^2

Solution

1. Step 1: Understand the recurrence meaning

   3T(n/3) means dividing problem into 3 equal parts recursively, plus n^2 extra work.

2. Step 2: Fix code to match recurrence

   Ensure code calls itself 3 times on n/3 size and does n^2 work outside recursion.

3. Final Answer:

   Change the recursive calls to 3T(n/3) and keep n^2 as extra work -> Option A

4. Quick Check:

   3 recursive calls on n/3 + n^2 work = 3T(n/3)+n^2 [OK]

Hint: Match recursive calls count and size to recurrence exactly [OK]

Common Mistakes:

• Changing extra work without fixing recursive calls
• Using wrong subproblem size like n-1
• Reducing calls to 2 instead of 3

5. You have a problem of size n that you divide into 4 subproblems each of size n/2. The extra work done outside the recursive calls is O(n^2). What is the time complexity T(n) of this divide and conquer algorithm?

hard

A. O(n^2 log n)

B. O(n^3)

C. O(n^2)

D. O(n log n)

Solution

1. Step 1: Write the recurrence relation

   Since there are 4 subproblems each size n/2 and extra work n^2, T(n) = 4T(n/2) + n^2.

2. Step 2: Apply Master Theorem

   Here, a=4, b=2, f(n)=n^2. Calculate log_b(a) = log_2(4) = 2. Since f(n) = Theta(n^2), it matches n^{log_b(a)}.

3. Step 3: Determine complexity

   By Master Theorem case 2, T(n) = Theta(n^2 log n).

4. Final Answer:

   O(n^2 log n) -> Option A

5. Quick Check:

   4 calls on half + n^2 work = n^2 log n [OK]

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

Common Mistakes:

• Ignoring the log factor in complexity
• Confusing number of subproblems with size
• Mistaking it for cubic or linear complexity