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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Merge Sort Call Count

What is the output of the following JavaScript code that counts the number of recursive calls in merge sort for an array of length 4?

DSA Javascript

let count = 0;
function mergeSort(arr) {
  count++;
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}
function merge(left, right) {
  let result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}
mergeSort([4, 3, 2, 1]);
console.log(count);

A 8

B 7

C 6

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 arrays of length 1. For length 4, calls are: 1 (whole), 2 (two halves), 4 (four single elements), total 7 calls.

🧠 Conceptual

intermediate

Recurrence Relation for Binary Search

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

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

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

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

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

💡 Hint

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

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

🔧 Debug

advanced

Identify the Error in Recurrence Calculation

Consider the following recurrence relation code snippet in JavaScript to calculate T(n) = 2T(n/2) + n. What error will occur when calling recurrence(1)?

DSA Javascript

function recurrence(n) {
  if (n === 1) return 1;
  return 2 * recurrence(n / 2) + n;
}
console.log(recurrence(1));

A Returns 1 without error

B Stack overflow due to infinite recursion

C Returns NaN due to floating point division

D TypeError because n is not an integer

💡 Hint

Check the base case and how n changes in recursive calls.

The base case returns 1 when n is exactly 1. Since n is divided by 2 each time, it reaches 1 exactly for powers of two, so no infinite recursion occurs and the function returns 1.

❓ Predict Output

advanced

Output of Recursive Fibonacci with Memoization

What is the output of the following JavaScript code that uses divide and conquer with memoization to compute fibonacci(5)?

DSA Javascript

function fibonacci(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}
console.log(fibonacci(5));

A 5

B 8

C 3

D 13

💡 Hint

Recall the Fibonacci sequence: 0,1,1,2,3,5,...

The function returns the 5th Fibonacci number (0-based index), which is 5.

🧠 Conceptual

expert

Mastering the Master Theorem Case

Given the recurrence relation T(n) = 4T(n/2) + n^2, which case of the Master Theorem applies and what is the asymptotic complexity?

A Case 2: T(n) = Θ(n^4)

B Case 1: T(n) = Θ(n^2)

C Case 3: T(n) = Θ(n^3)

D Case 2: T(n) = Θ(n^2 log n)

💡 Hint

Compare n^log_b(a) with f(n) where a=4, b=2, f(n)=n^2.

Here, a=4, b=2, so n^log_b(a) = n^2. Since f(n) = n^2, it matches case 2 of the Master Theorem, so T(n) = Θ(n^2 log n).

Practice

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

easy

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

B. Use a single loop to iterate through all elements

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 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 C

4. Quick Check:

   Divide and conquer = split, 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 one loop
• Mixing it with dynamic programming

2. Which of the following is the correct syntax for the recurrence relation of Merge Sort?

easy

A. T(n) = 3T(n/3) + O(log n)

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

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

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

Solution

1. Step 1: Recall Merge Sort recurrence

   Merge Sort splits array into two halves, sorts each half, then merges in O(n).

2. Step 2: Write recurrence form

   It calls itself twice on half size (2T(n/2)) plus linear merge time 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)
• Adding O(n^2) instead of O(n)
• Confusing with Quick Sort recurrence

3. What is the output of the following JavaScript function that uses divide and conquer?

function sumArray(arr) {
  if (arr.length === 1) return arr[0];
  const mid = Math.floor(arr.length / 2);
  return sumArray(arr.slice(0, mid)) + sumArray(arr.slice(mid));
}
console.log(sumArray([2, 4, 6, 8]));

medium

A. 20

B. 24

C. 10

D. Error

Solution

1. Step 1: Understand the function behavior

   The function splits the array into halves recursively and sums elements.

2. Step 2: Trace the calls for [2,4,6,8]

   Split into [2,4] and [6,8], sumArray([2,4]) = 6, sumArray([6,8]) = 14, total 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Sum of 2+4+6+8 = 20 [OK]

Hint: Divide array, sum halves, add results [OK]

Common Mistakes:

• Confusing slice indices causing wrong sums
• Assuming function returns array instead of sum
• Forgetting base case for single element

4. Identify the error in this divide and conquer function to find the maximum element:

function findMax(arr) {
  if (arr.length === 1) return arr[0];
  const mid = Math.floor(arr.length / 2);
  const leftMax = findMax(arr.slice(0, mid));
  const rightMax = findMax(arr.slice(mid));
  return leftMax > rightMax ? leftMax : rightMax;
}
console.log(findMax([]));

medium

A. Fails on empty array input causing infinite recursion

B. Incorrect comparison operator used

C. No error, works correctly

D. Slices do not split array properly

Solution

1. Step 1: Check base case for empty array

   The function does not handle empty array input, so arr.length === 0 is not checked.

2. Step 2: Understand recursion on empty array

   Calling findMax([]) leads to infinite recursion because base case is only for length 1.

3. Final Answer:

   Fails on empty array input causing infinite recursion -> Option A

4. Quick Check:

   Empty input needs base case to avoid infinite calls [OK]

Hint: Always check for empty input base case [OK]

Common Mistakes:

• Ignoring empty array edge case
• Assuming slice always returns non-empty array
• Thinking comparison operator is wrong

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

hard

A. O(log n)

B. O(n^2)

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

4. Final Answer:

   O(n log n) -> Option D

5. Quick Check:

   Master Theorem case 2 = n log n [OK]

Hint: Compare f(n) to n^log_b(a) for Master Theorem [OK]

Common Mistakes:

• Confusing log base or parameters a and b
• Choosing wrong Master Theorem case
• Ignoring the extra n term in recurrence