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.