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

Concept Flow - Divide and Conquer Strategy and Recurrence Relations

Divide Problem into Subproblems

↓

Solve Each Subproblem Recursively

↓

Combine Subproblem Solutions

↓

Final Solution

↓

Recurrence Relation

↓

Express Time as T(n) = a*T(n/b) + f(n)

↓

Solve Recurrence to Find Complexity

Divide and conquer splits a problem into smaller parts, solves each part, then combines results. Recurrence relations express the time cost of this process.

Execution Sample

DSA C

void mergeSort(int arr[], int l, int r) {
  if (l < r) {
    int m = l + (r - l) / 2;
    mergeSort(arr, l, m);
    mergeSort(arr, m + 1, r);
    merge(arr, l, m, r);
  }
}

This code divides the array into halves recursively, sorts each half, then merges them.

Execution Table

Step	Operation	Subproblem Size	Recurrence Expression	Visual State
1	Divide array of size n into two halves	n	T(n) = 2*T(n/2) + O(n)	Array split into two parts
2	Recursively sort left half	n/2	T(n/2) = 2*T(n/4) + O(n/2)	Left half split further
3	Recursively sort right half	n/2	T(n/2) = 2*T(n/4) + O(n/2)	Right half split further
4	Combine sorted halves by merging	n	O(n)	Two sorted halves merged
5	Base case reached when subproblem size = 1	1	T(1) = O(1)	Single element array (sorted)
6	Recurrence solved using Master Theorem	-	T(n) = O(n log n)	Overall sorting time complexity
7	End	-	-	Sorting complete

💡 Recursion ends when subproblem size reaches 1, then merges combine results back up.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
n (problem size)	n	n/2	n/4	n/4	n	n
T(n) (time)	T(n)	2*T(n/2)+O(n)	2*T(n/4)+O(n/2)	2*T(n/4)+O(n/2)	O(n)	O(n log n)
Array state	Unsorted array	Split into halves	Left half split	Right half split	Merged halves	Sorted array

Key Moments - 3 Insights

Why do we express the time as T(n) = a*T(n/b) + f(n)?

Because the problem divides into 'a' subproblems each of size n/b, and f(n) is the time to divide and combine. This is shown in execution_table rows 1 and 2.

When does the recursion stop in divide and conquer?

Recursion stops when the subproblem size is 1, which is the base case shown in execution_table row 5.

How does solving the recurrence relate to overall time complexity?

Solving the recurrence (row 6) gives the total time complexity, combining all recursive calls and merges.

Visual Quiz - 3 Questions

Look at the execution_table, what is the recurrence expression at Step 2?

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

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

C T(1) = O(1)

D T(n) = O(n log n)

💡 Hint

Check the 'Recurrence Expression' column at Step 2 in the execution_table.

At which step does the recursion reach the base case?

A Step 5

B Step 4

C Step 3

D Step 6

💡 Hint

Look for the step mentioning subproblem size = 1 in the execution_table.

If the problem was divided into 4 subproblems instead of 2, how would the recurrence expression at Step 1 change?

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

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

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

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

💡 Hint

Recall the formula T(n) = a*T(n/b) + f(n), where 'a' is number of subproblems and 'b' is size division.

Concept Snapshot

Divide and Conquer splits a problem into smaller parts,
solves each recursively, then combines results.
Time is expressed as T(n) = a*T(n/b) + f(n).
Solve recurrence to find complexity (e.g., O(n log n) for merge sort).
Base case stops recursion when problem size is 1.

Full Transcript

Divide and conquer strategy breaks a problem into smaller subproblems, solves each recursively, and then combines the solutions. The time taken is expressed using a recurrence relation T(n) = a*T(n/b) + f(n), where 'a' is the number of subproblems, 'n/b' is the size of each subproblem, and f(n) is the time to divide and combine. The recursion stops when the subproblem size reaches 1, which is the base case. Solving the recurrence relation using methods like the Master Theorem gives the overall time complexity, such as O(n log n) for merge sort. This approach helps analyze and understand the efficiency of divide and conquer algorithms.