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.

Practice

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

easy

A. Use a single loop to solve the problem iteratively

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

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 Divide and Conquer approach

   It splits a big problem into smaller parts that are easier to solve.

2. Step 2: Combine solutions of subproblems

   After solving smaller parts, their results are combined 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 = Break, Solve, Combine [OK]

Hint: Divide big problem into parts, solve parts, then combine [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 on an array of size n?

easy

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

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

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

D. T(n) = 3T(n/3) + O(n^2)

Solution

1. Step 1: Recall Merge Sort process

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

2. Step 2: Write recurrence relation

   It calls itself twice on size n/2 plus linear merge step, so T(n) = 2T(n/2) + O(n).

3. Final Answer:

   T(n) = 2T(n/2) + O(n) -> Option B

4. Quick Check:

   Merge Sort recurrence = 2 halves + merge O(n) [OK]

Hint: Two halves plus linear merge step means 2T(n/2)+n [OK]

Common Mistakes:

• Using T(n-1) instead of T(n/2)
• Ignoring the merge step cost
• Confusing with quicksort recurrence

3. Consider the following C code implementing a divide and conquer function:

int func(int n) {
    if (n <= 1) return 1;
    return func(n/2) + func(n/2) + n;
}

What is the time complexity T(n) of this function?

medium

A. O(n^2)

B. O(n)

C. O(log n)

D. O(n log n)

Solution

1. Step 1: Identify recurrence relation

   The function calls itself twice on n/2 plus does O(n) work, so T(n) = 2T(n/2) + n.

2. Step 2: Solve recurrence using Master Theorem

   For T(n) = 2T(n/2) + n, the solution is O(n log n).

3. Final Answer:

   O(n log n) -> Option D

4. Quick Check:

   2 calls on half + linear work = n log n [OK]

Hint: Two halves plus linear work means n log n time [OK]

Common Mistakes:

• Thinking it is O(n) by ignoring recursive calls
• Confusing with O(log n) for single call
• Mistaking it for quadratic O(n^2)

4. The following recurrence relation is given:

T(n) = 3T(n/3) + n^2

There is a mistake in the code implementing this recurrence. Which fix will correct the recurrence to match the intended divide and conquer approach?

medium

A. Change the recursive calls to 3T(n/3) and keep n^2 as extra work

B. Change the extra work from n^2 to n log n

C. Change the recursive calls to T(n-1) and keep n^2

D. Change the recursive calls to 2T(n/2) and keep n^2

Solution

1. Step 1: Understand the recurrence meaning

   3T(n/3) means dividing problem into 3 equal parts recursively, plus n^2 extra work.

2. Step 2: Fix code to match recurrence

   Ensure code calls itself 3 times on n/3 size and does n^2 work outside recursion.

3. Final Answer:

   Change the recursive calls to 3T(n/3) and keep n^2 as extra work -> Option A

4. Quick Check:

   3 recursive calls on n/3 + n^2 work = 3T(n/3)+n^2 [OK]

Hint: Match recursive calls count and size to recurrence exactly [OK]

Common Mistakes:

• Changing extra work without fixing recursive calls
• Using wrong subproblem size like n-1
• Reducing calls to 2 instead of 3

5. You have a problem of size n that you divide into 4 subproblems each of size n/2. The extra work done outside the recursive calls is O(n^2). What is the time complexity T(n) of this divide and conquer algorithm?

hard

A. O(n^2 log n)

B. O(n^3)

C. O(n^2)

D. O(n log n)

Solution

1. Step 1: Write the recurrence relation

   Since there are 4 subproblems each size n/2 and extra work n^2, T(n) = 4T(n/2) + n^2.

2. Step 2: Apply Master Theorem

   Here, a=4, b=2, f(n)=n^2. Calculate log_b(a) = log_2(4) = 2. Since f(n) = Theta(n^2), it matches n^{log_b(a)}.

3. Step 3: Determine complexity

   By Master Theorem case 2, T(n) = Theta(n^2 log n).

4. Final Answer:

   O(n^2 log n) -> Option A

5. Quick Check:

   4 calls on half + n^2 work = n^2 log n [OK]

Hint: Use Master Theorem: compare f(n) with n^{log_b(a)} [OK]

Common Mistakes:

• Ignoring the log factor in complexity
• Confusing number of subproblems with size
• Mistaking it for cubic or linear complexity