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.