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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Merge Sort Call Count

Consider the following TypeScript function that counts how many times the mergeSort function is called for an array of length n. What is the output when calling mergeSortCount([3,1,4,1,5])?

DSA Typescript

function mergeSortCount(arr: number[], count = {calls: 0}): number {
  count.calls++;
  if (arr.length <= 1) return count.calls;
  const mid = Math.floor(arr.length / 2);
  mergeSortCount(arr.slice(0, mid), count);
  mergeSortCount(arr.slice(mid), count);
  return count.calls;
}

console.log(mergeSortCount([3,1,4,1,5]));

A 9

B 11

C 7

D 5

💡 Hint

Think about how many times the function splits the array and calls itself recursively.

The mergeSort function calls itself recursively a total of 9 times for an array of length 5 (2n - 1 = 9 calls).

🧠 Conceptual

intermediate

Recurrence Relation for Binary Search

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

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) = T(n/2) + O(n)

💡 Hint

Binary search splits the array into half and does a constant amount of work each step.

Binary search divides the problem size by 2 each time and does constant work to compare the middle element, so the recurrence is T(n) = T(n/2) + O(1).

🔧 Debug

advanced

Identify the Error in Recurrence Calculation

The following TypeScript function attempts to compute the number of operations for a divide and conquer algorithm with recurrence T(n) = 2T(n/2) + n. What error causes incorrect output?

DSA Typescript

function operationsCount(n: number): number {
  if (n <= 1) return 1;
  return 2 * operationsCount(Math.floor(n / 2)) + n;
}

console.log(operationsCount(8));

A The function should multiply n by 2 instead of adding n.

B The base case should be n === 0 instead of n <= 1.

C The function uses floating point division instead of integer division, causing incorrect results.

D The function should return n instead of 1 in the base case.

💡 Hint

Check how the recursive calls reduce n and if they reach the base case.

Using n / 2 with floating point division can cause incorrect results for inputs where n/2 is not integer, as the recurrence assumes integer division.

🚀 Application

advanced

Calculate Time Complexity from Recurrence

Given the recurrence relation T(n) = 3T(n/3) + n, what is the time complexity in Big O notation?

A O(n)

B O(n^2)

C O(log n)

D O(n log n)

💡 Hint

Use the Master Theorem to solve the recurrence.

Here a=3, b=3, f(n)=n. Since f(n) = Theta(n^{log_b a}), time complexity is O(n log n).

❓ Predict Output

expert

Output of Recursive Function with Custom Recurrence

What is the output of the following TypeScript code?

DSA Typescript

function customRecurrence(n: number): number {
  if (n < 1) return 0;
  return customRecurrence(Math.floor(n / 3)) + customRecurrence(Math.floor(2 * n / 3)) + n;
}

console.log(customRecurrence(9));

A 27

B 33

C 31

D 29

💡 Hint

Trace the recursive calls carefully and sum the results.

The function splits n into floor(n/3) and floor(2n/3), sums their results plus n. For n=9, the total is 33.

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 the divide and conquer approach

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

2. Step 2: Combine the solutions of smaller parts

   After solving subproblems, their results are merged 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 problems into smaller parts, solve, then merge [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) = 2T(n/2) + O(n)

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

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

Solution

1. Step 1: Recall Merge Sort process

   Merge Sort splits array into two halves, sorts each half, then merges.

2. Step 2: Write recurrence relation

   It calls itself twice on half size (2T(n/2)) plus merging cost O(n).

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 with recursive calls
• Choosing cubic or quadratic terms incorrectly

3. What is the output of the following TypeScript function that uses divide and conquer to find the maximum element?

function findMax(arr: number[], left: number, right: number): number {
  if (left === right) return arr[left];
  const mid = Math.floor((left + right) / 2);
  const maxLeft = findMax(arr, left, mid);
  const maxRight = findMax(arr, mid + 1, right);
  return maxLeft > maxRight ? maxLeft : maxRight;
}

const array = [3, 5, 1, 8, 2];
console.log(findMax(array, 0, array.length - 1));

medium

A. 3

B. 5

C. 8

D. 2

Solution

1. Step 1: Understand the function logic

   The function splits the array into halves recursively and compares max values.

2. Step 2: Trace the recursive calls on array [3,5,1,8,2]

   Max in left half [3,5,1] is 5; max in right half [8,2] is 8; final max is 8.

3. Final Answer:

   8 -> Option C

4. Quick Check:

   Max element found by divide and conquer = 8 [OK]

Hint: Divide array, find max in halves, pick bigger [OK]

Common Mistakes:

• Returning min instead of max
• Incorrect mid calculation causing infinite recursion
• Mixing indices causing wrong subarray

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

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

This recurrence is supposed to represent the time complexity of a divide and conquer algorithm similar to Merge Sort.

medium

A. Change O(n^2) to O(n) because merging takes linear time

B. Change 2T(n/2) to T(n-1) because it is not dividing

C. Change O(n^2) to O(log n) because merging is logarithmic

D. No error, the recurrence is correct

Solution

1. Step 1: Analyze the merging cost in divide and conquer

   In Merge Sort-like algorithms, merging two halves takes O(n) time, not O(n^2).

2. Step 2: Correct the recurrence relation

   Replace O(n^2) with O(n) to reflect the linear merging cost.

3. Final Answer:

   Change O(n^2) to O(n) because merging takes linear time -> Option A

4. Quick Check:

   Merging cost = O(n), not O(n^2) [OK]

Hint: Merging in divide and conquer is linear, not quadratic [OK]

Common Mistakes:

• Assuming merging is quadratic
• Changing recursive calls incorrectly
• Ignoring the cost of merging step

5. Given the recurrence relation T(n) = 3T(n/3) + n, what is the time complexity of the algorithm using the Master Theorem?

hard

A. O(log n)

B. O(n^2)

C. O(n^{\log_3 3}) = O(n)

D. O(n log n)

Solution

1. Step 1: Identify parameters for Master Theorem

   Here, a=3, b=3, f(n)=n. Calculate log_b(a) = log_3(3) = 1.

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

   f(n) = n and n^{log_b(a)} = n^1 = n, so f(n) = Theta(n^{log_b(a)}).

3. Step 3: Apply Master Theorem case 2

   When f(n) = Theta(n^{log_b(a)}), T(n) = Theta(n^{log_b(a)} log n) = Theta(n log n).

4. Final Answer:

   O(n log n) -> Option D

5. Quick Check:

   Master Theorem case 2 gives O(n log n) [OK]

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

Common Mistakes:

• Ignoring the log factor in case 2
• Confusing log base or parameters a and b
• Choosing linear time incorrectly