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 that counts the number of recursive calls made by merge sort on an array of size 4. What is the printed output?

DSA C++

int count = 0;

void mergeSort(int arr[], int l, int r) {
    count++;
    if (l >= r) return;
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    // merging code omitted for brevity
}

int main() {
    int arr[4] = {4, 3, 2, 1};
    mergeSort(arr, 0, 3);
    std::cout << count << std::endl;
    return 0;
}

A 6

B 7

C 8

D 5

💡 Hint

Count how many times mergeSort is called including the base cases.

The mergeSort function is called once for the whole array, then recursively for each half until single elements are reached.

For size 4, calls are: mergeSort(0,3), mergeSort(0,1), mergeSort(0,0), mergeSort(1,1), mergeSort(2,3), mergeSort(2,2), mergeSort(3,3) totaling 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?

A None of the above

B Case 1: f(n) = O(n^{log_b a - ε})

C Case 2: f(n) = Θ(n^{log_b a} * log^k n)

D Case 3: f(n) = Ω(n^{log_b a + ε}) and regularity condition holds

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

f(n) = n = n^1 = Ω(n^{0.792 + ε}) for ε ≈ 0.208.

Regularity condition: a f(n/4) = 3*(n/4) = 0.75n ≤ c n for c=0.75 < 1, holds for all n ≥ 1.

Thus, Case 3 applies: T(n) = Θ(n).

🔧 Debug

advanced

Identify the Error in Recurrence Implementation

What error will occur when running this C++ code that tries to compute T(n) = 2T(n/2) + n using recursion for n=1?

DSA C++

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

int main() {
    std::cout << T(0) << std::endl;
    return 0;
}

A Stack overflow due to infinite recursion

B Returns 1 without error

C Division by zero error

D Compilation error due to missing return

💡 Hint

Check what happens when n=0 is passed to the function.

The base case is for n==1, but main calls T(0).

For n=0, it calls T(0/2)=T(0) again, causing infinite recursion and stack overflow.

🚀 Application

advanced

Time Complexity of Strassen's Matrix Multiplication

Strassen's algorithm multiplies two n×n matrices using 7 recursive multiplications of size n/2 and O(n^2) additions. What is the time complexity T(n) expressed using Big O notation?

A O(n^{log_2 7})

B O(n^3)

C O(n^{2.5})

D O(n^{log_7 2})

💡 Hint

Use the Master Theorem with a=7, b=2, and f(n)=O(n^2).

Here, a=7, b=2, so log_b a = log_2 7 ≈ 2.807.

Since f(n) = O(n^2) which is smaller than n^{log_b a}, the time complexity is O(n^{log_2 7}).

🧠 Conceptual

expert

Recurrence Relation for Binary Search and Its Solution

What is the recurrence relation for the time complexity of binary search on a sorted array of size n, and what is its closed-form solution?

A T(n) = T(n-1) + O(1), solution: O(n)

B T(n) = 2T(n/2) + O(1), solution: O(n)

C T(n) = T(n/2) + O(1), solution: O(log n)

D T(n) = T(n/2) + O(n), solution: O(n)

💡 Hint

Binary search halves the problem size each step and does constant work per step.

Binary search splits the array into halves each step, so T(n) = T(n/2) + O(1).

Solving this recurrence gives O(log n) time complexity.

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 iterate through all elements

D. Store all intermediate results to avoid repeated calculations

Solution

1. Step 1: Understand Divide and Conquer concept

   Divide and conquer splits a problem into smaller parts, solves each part, then merges results.

2. Step 2: Compare options

   Break the problem into smaller subproblems, solve them independently, then combine results correctly describes this process. Options B, C, and D describe other strategies like brute force or dynamic programming.

3. Final Answer:

   Break the problem into smaller subproblems, solve them independently, then combine results -> Option A

4. Quick Check:

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

Hint: Divide and conquer means split, solve, then merge results [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?

easy

A. T(n) = 3T(n/3) + O(n^2)

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

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

D. T(n) = T(n/2) + O(log n)

Solution

1. Step 1: Recall Merge Sort recurrence

   Merge Sort divides array into two halves, sorts each half (2T(n/2)) and merges in O(n).

2. Step 2: Match with options

   T(n) = 2T(n/2) + O(n) matches 2T(n/2) + O(n). Others describe different algorithms or complexities.

3. Final Answer:

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

4. Quick Check:

   Merge Sort recurrence = 2T(n/2) + n [OK]

Hint: Merge Sort splits in two and merges in linear time [OK]

Common Mistakes:

• Using T(n-1) instead of T(n/2)
• Confusing merge cost with recursive calls
• Choosing quadratic terms incorrectly

3. What is the output of the following C++ function call:

int count = 0;
int func(int n) {
  if (n <= 1) return 1;
  count++;
  return func(n/2) + func(n/2);
}
int main() {
  func(8);
  std::cout << count;
  return 0;
}

medium

A. 15

B. 7

C. 8

D. 6

Solution

1. Step 1: Understand recursion calls and count increments

   func(8) calls func(4) twice, each func(4) calls func(2) twice, and so on until n <= 1.

2. Step 2: Count increments at each call

   Count increments at each non-base call. The recursion tree has 15 non-base calls (all calls except those where n <= 1). Thus, count increments 15 times.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Count increments for each non-base call = 15 [OK]

Hint: Count increments at each non-base recursive call [OK]

Common Mistakes:

• Counting base case calls
• Not doubling calls for each recursion
• Miscounting due to integer division

4. Identify the error in the following recurrence relation and fix it:

T(n) = 2T(n/2) + n^2 for n > 1
T(1) = 1

What is the correct time complexity?

medium

A. O(n log n)

B. O(n^2)

C. O(n^2 log n)

D. O(n)

Solution

1. Step 1: Analyze the recurrence relation

   T(n) = 2T(n/2) + n^2 means dividing problem into two halves and combining in n^2 time.

2. Step 2: Apply Master Theorem

   Here, a=2, b=2, log_b a = 1, f(n)=n^2 = Ω(n^{1 + ε}) for some ε > 0 (case 3). Thus, time complexity is Θ(n^2) = O(n^2).

3. Final Answer:

   O(n^2) -> Option B

4. Quick Check:

   Master Theorem with f(n)=n^2 gives O(n^2) [OK]

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

Common Mistakes:

• Assuming O(n log n) without checking f(n)
• Ignoring the power of n in f(n)
• Misapplying Master Theorem cases

5. Given the recurrence relation

T(n) = 3T(n/3) + n / log n

Using the Master Theorem, what is the asymptotic time complexity of T(n)?

hard

A. O(n)

B. O(n^{log_3 3})

C. O(n log n)

D. O(n log log n)

Solution

1. Step 1: Identify parameters for Master Theorem

   a=3, b=3, so n^{log_b a} = n^{log_3 3} = n^1 = n.

2. Step 2: Compare f(n) = n / log n with n^{log_b a} = n

   f(n) grows slower than n by a factor of log n. This is a case where f(n) = n / log n = n^{1} / log n.

3. Step 3: Apply Master Theorem case 2 variant

   Since f(n) = n / log n = n^{1} / log n, which is smaller than n^{1} by a log factor, the complexity is O(n log log n).

4. Final Answer:

   O(n log log n) -> Option D

5. Quick Check:

   Master Theorem with f(n) = n / log n gives O(n log log n) [OK]

Hint: Compare f(n) to n^{log_b a} carefully for log factors [OK]

Common Mistakes:

• Ignoring the log factor in f(n)
• Choosing O(n) or O(n log n) incorrectly
• Miscomputing log base