Divide and Conquer Strategy and Recurrence Relations in DSA Javascript - Execution Trace

Concept Flow - Divide and Conquer Strategy and Recurrence Relations

Start Problem

↓

Divide Problem into Subproblems

↓

Conquer: Solve Subproblems Recursively

↓

Combine Subproblem Solutions

↓

Return Final Solution

The problem is split into smaller parts, each part is solved, then results are combined to solve the original problem.

Execution Sample

DSA Javascript

function divideAndConquer(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = divideAndConquer(arr.slice(0, mid));
  const right = divideAndConquer(arr.slice(mid));
  return merge(left, right);
}

This code splits an array into halves recursively and merges sorted halves (like merge sort).

Execution Table

Step	Operation	Subproblem Size	Recursion Depth	Action	Resulting State
1	Start with array [8,3,5,4]	4	0	Divide into [8,3] and [5,4]	[8,3], [5,4]
2	Divide left [8,3]	2	1	Divide into [8] and [3]	[8], [3]
3	Base case reached for [8]	1	2	Return [8]	[8]
4	Base case reached for [3]	1	2	Return [3]	[3]
5	Merge [8] and [3]	2	1	Compare and merge	[3,8]
6	Divide right [5,4]	2	1	Divide into [5] and [4]	[5], [4]
7	Base case reached for [5]	1	2	Return [5]	[5]
8	Base case reached for [4]	1	2	Return [4]	[4]
9	Merge [5] and [4]	2	1	Compare and merge	[4,5]
10	Merge [3,8] and [4,5]	4	0	Compare and merge	[3,4,5,8]
11	Return final sorted array	4	0	Done	[3,4,5,8]

💡 All subproblems reached base case of size 1, merged back to final sorted array.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	After Step 10	Final
arr	[8,3,5,4]	[8,3]	[3,8]	[4,5]	[3,4,5,8]	[3,4,5,8]
mid	undefined	2	undefined	undefined	undefined	undefined
left	undefined	[8]	[3,8]	[4,5]	[3,4,5,8]	[3,4,5,8]
right	undefined	[3]	undefined	undefined	undefined	undefined
recursionDepth	0	1	2	2	1	0

Key Moments - 3 Insights

Why do we stop dividing when the subproblem size is 1?

Because a single element is already sorted or solved, so no further division is needed. See execution_table rows 3 and 4 where base cases return immediately.

How does the recursion depth relate to the size of subproblems?

Each recursion level halves the problem size, increasing depth by 1. Execution_table shows depth increasing as array size halves (rows 2,3,4).

Why do we combine results after solving subproblems?

Because the original problem solution depends on merging subproblem solutions. Execution_table rows 5,9,10 show merging steps combining sorted halves.

Visual Quiz - 3 Questions

Look at the execution_table, what is the subproblem size at step 6?

A 1

B 2

C 4

D 0

💡 Hint

Check the 'Subproblem Size' column at step 6 in execution_table.

At which step does the recursion depth return to 0 after dividing?

A Step 10

B Step 3

C Step 5

D Step 7

💡 Hint

Look at the 'Recursion Depth' column and find when it goes back to 0 after deeper calls.

If the initial array had 8 elements instead of 4, how would the recursion depth change?

A It would decrease by 1

B It would stay the same

C It would increase by 1

D It would double

💡 Hint

Recursion depth increases as problem size halves; doubling size adds one more division level.

Concept Snapshot

Divide and Conquer splits a problem into smaller parts,
solves each part recursively, then combines results.
Recurrence relations describe time cost: T(n) = aT(n/b) + f(n).
Base case stops recursion when problem is small enough.
Example: Merge Sort divides array, sorts halves, merges them.

Full Transcript

Divide and Conquer is a strategy where a problem is split into smaller subproblems. Each subproblem is solved recursively until it reaches a base case, usually when the problem size is 1 or very small. Then, the solutions to subproblems are combined to form the solution to the original problem. The execution sample shows a recursive function that splits an array into halves, sorts each half, and merges them. The execution table traces each step, showing how the array is divided, base cases reached, and merges performed. Variables like recursion depth and subproblem size change as the recursion progresses. Key moments clarify why recursion stops at size 1, how recursion depth relates to problem size, and why combining results is necessary. The visual quiz tests understanding of subproblem sizes, recursion depth, and effects of input size on recursion. The concept snapshot summarizes the divide and conquer approach and its relation to recurrence relations.

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