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

Concept Flow - Divide and Conquer Strategy and Recurrence Relations

Divide Problem into Subproblems

↓

Recursively Solve Each Subproblem

↓

Combine Subproblem Solutions

↓

Final Solution

↓

Form Recurrence Relation

↓

Analyze Recurrence to Find Complexity

The problem is split into smaller parts, each solved recursively, then combined. This process forms a recurrence relation used to analyze time complexity.

Execution Sample

DSA Typescript

function mergeSort(arr: number[]): number[] {
  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);
}

This code divides an array into halves recursively and merges sorted halves, illustrating divide and conquer.

Execution Table

Step	Operation	Subproblem Size	Recursion Depth	Action	Visual State
1	Divide array [8,3,5,4]	4	0	Split into [8,3] and [5,4]	[8,3,5,4]
2	Divide subarray [8,3]	2	1	Split 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	Merge to [3,8]	[3,8]
6	Divide subarray [5,4]	2	1	Split 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	Merge to [4,5]	[4,5]
10	Merge [3,8] and [4,5]	4	0	Merge to [3,4,5,8]	[3,4,5,8]
11	Recurrence formed: T(n) = 2T(n/2) + O(n)	n	-	Analyze to find O(n log n)	[Sorted array]

💡 All subproblems reduced to size 1 (base case), merged back to final sorted array.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 5	After Step 10	Final
arr	[8,3,5,4]	[8,3] and [5,4]	[8] and [3]	[3,8]	[3,4,5,8]	[3,4,5,8]
subproblem size	4	2	1	2	4	4
recursion depth	0	1	2	1	0	0

Key Moments - 3 Insights

Why do we stop dividing when subproblem size is 1?

Because a single element is already sorted, so the base case returns immediately as shown in steps 3 and 4.

How does the recurrence T(n) = 2T(n/2) + O(n) represent the algorithm?

It shows the problem splits into two halves (2T(n/2)) and merging takes linear time (O(n)), as summarized in step 11.

Why does recursion depth increase when dividing and decrease when merging?

Each division adds a level of recursion (steps 1,2), and merging returns back up reducing depth (steps 5,10), reflecting the call stack.

Visual Quiz - 3 Questions

Look at the execution table, what is the subproblem size at step 6?

A 4

B 1

C 2

D 0

💡 Hint

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

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

A Step 5

B Step 10

C Step 3

D Step 1

💡 Hint

Look at the 'Recursion Depth' column in the execution_table and find when it goes back to 0.

If the array size doubles, how does the recurrence relation change?

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

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

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

D T(2n) = T(n) + O(n)

💡 Hint

Recall the recurrence T(n) = 2T(n/2) + O(n) and consider doubling n.

Concept Snapshot

Divide and Conquer splits a problem into smaller parts,
solves each recursively, then combines results.
Recurrence relations express time as T(n) = aT(n/b) + f(n).
Analyzing recurrence finds algorithm complexity.
Example: Merge Sort uses T(n) = 2T(n/2) + O(n) → O(n log n).

Full Transcript

Divide and Conquer strategy breaks a problem into smaller subproblems, solves each recursively, and combines their solutions. This process forms a recurrence relation that expresses the time complexity. For example, merge sort divides an array into halves until single elements remain, then merges sorted halves. The recurrence relation T(n) = 2T(n/2) + O(n) describes this, where 2T(n/2) is the time for recursive calls and O(n) is the merge time. Analyzing this recurrence shows merge sort runs in O(n log n) time.

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