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

Concept Flow - Divide and Conquer Strategy and Recurrence Relations

Divide Problem

↓

Divide into Subproblems

↓

Conquer Subproblems Recursively

↓

Combine Subproblem Solutions

↓

Final Solution

The problem is split into smaller parts, solved separately, then combined to get the final answer.

Execution Sample

DSA C++

int divideAndConquer(int n) {
  if (n == 1) return 1;
  int left = divideAndConquer(n/2);
  int right = divideAndConquer(n/2);
  return left + right;
}

This code splits the input n into halves recursively until 1, then sums results back up.

Execution Table

Step	Operation	Current n	Recursive Calls	Return Value	Visual State
1	Call divideAndConquer(4)	4	Calls divideAndConquer(2) twice	Pending	Root call with n=4
2	Call divideAndConquer(2)	2	Calls divideAndConquer(1) twice	Pending	Left subtree with n=2
3	Call divideAndConquer(1)	1	Base case reached	1	Leaf node with n=1 returns 1
4	Call divideAndConquer(1)	1	Base case reached	1	Leaf node with n=1 returns 1
5	Return from divideAndConquer(2)	2	Both calls returned 1	2	Sum left and right: 1+1=2
6	Call divideAndConquer(2)	2	Calls divideAndConquer(1) twice	Pending	Right subtree with n=2
7	Call divideAndConquer(1)	1	Base case reached	1	Leaf node with n=1 returns 1
8	Call divideAndConquer(1)	1	Base case reached	1	Leaf node with n=1 returns 1
9	Return from divideAndConquer(2)	2	Both calls returned 1	2	Sum left and right: 1+1=2
10	Return from divideAndConquer(4)	4	Both calls returned 2	4	Sum left and right: 2+2=4
11	End	-	-	-	All recursive calls complete

💡 Recursion ends when n == 1 (base case), then results combine back up.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 6	After Step 9	Final
n	4	2	2	2	2	4
left	-	Pending	1	Pending	1	2 or 4 (depending on call)
right	-	Pending	1	Pending	1	2 or 4 (depending on call)
Return Value	-	Pending	2	Pending	2	4

Key Moments - 3 Insights

Why does the recursion stop when n equals 1?

Because the base case is defined at n == 1 (see steps 3,4,7,8 in execution_table), which prevents infinite recursion.

How do the results from subproblems combine to form the final answer?

After both recursive calls return their results, they are summed (steps 5,9,10), showing how subproblem solutions combine.

Why are there two recursive calls with n/2 each time?

Because the problem divides into two equal parts (divide step), each solved recursively (see steps 2 and 6).

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value at step 5?

A 1

B 4

C 2

D Pending

💡 Hint

Check the 'Return Value' column at step 5 in execution_table.

At which step does the recursion reach the base case for the first time?

A Step 1

B Step 3

C Step 2

D Step 5

💡 Hint

Look for 'Base case reached' in the 'Operation' column in execution_table.

If the initial n was 8 instead of 4, how would the number of recursive calls change?

A It would double

B It would stay the same

C It would halve

D It would increase but less than double

💡 Hint

Consider how dividing n by 2 repeatedly affects the number of calls in execution_table.

Concept Snapshot

Divide and Conquer splits a problem into smaller parts,
solves each recursively, then combines results.
Base case stops recursion (e.g., n == 1).
Recurrence relations describe time complexity.
Example: T(n) = 2T(n/2) + O(1) for splitting and combining.

Full Transcript

Divide and Conquer breaks a problem into smaller subproblems, solves each one recursively, and then combines their solutions to solve the original problem. The recursion stops at a base case, often when the problem size is 1. The example code shows this by calling itself twice with half the input size until it reaches 1, then sums the results back up. The execution table traces each recursive call, showing when the base case is reached and how results combine. Key points include understanding the base case, how recursive calls split the problem, and how results combine. Recurrence relations like T(n) = 2T(n/2) + O(1) help analyze the time complexity of such algorithms.

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

   Divide and conquer splits a problem into smaller parts, solves each part, then merges results.

2. Step 2: Compare options

   Break the problem into smaller subproblems, solve them independently, then combine results correctly describes this process. Options B, C, and D describe other strategies like brute force or dynamic programming.

3. Final Answer:

   Break the problem into smaller subproblems, solve them independently, then combine results -> Option A

4. Quick Check:

   Divide and Conquer = Break, 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 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) = T(n-1) + O(1)

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

D. T(n) = T(n/2) + O(log n)

Solution

1. Step 1: Recall Merge Sort recurrence

   Merge Sort divides array into two halves, sorts each half (2T(n/2)) and merges in O(n).

2. Step 2: Match with options

   T(n) = 2T(n/2) + O(n) matches 2T(n/2) + O(n). Others describe different algorithms or complexities.

3. Final Answer:

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

4. Quick Check:

   Merge Sort recurrence = 2T(n/2) + n [OK]

Hint: Merge Sort splits in two and merges in linear time [OK]

Common Mistakes:

• Using T(n-1) instead of T(n/2)
• Confusing merge cost with recursive calls
• Choosing quadratic terms incorrectly

3. What is the output of the following C++ function call:

int count = 0;
int func(int n) {
  if (n <= 1) return 1;
  count++;
  return func(n/2) + func(n/2);
}
int main() {
  func(8);
  std::cout << count;
  return 0;
}

medium

A. 15

B. 7

C. 8

D. 6

Solution

1. Step 1: Understand recursion calls and count increments

   func(8) calls func(4) twice, each func(4) calls func(2) twice, and so on until n <= 1.

2. Step 2: Count increments at each call

   Count increments at each non-base call. The recursion tree has 15 non-base calls (all calls except those where n <= 1). Thus, count increments 15 times.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Count increments for each non-base call = 15 [OK]

Hint: Count increments at each non-base recursive call [OK]

Common Mistakes:

• Counting base case calls
• Not doubling calls for each recursion
• Miscounting due to integer division

4. Identify the error in the following recurrence relation and fix it:

T(n) = 2T(n/2) + n^2 for n > 1
T(1) = 1

What is the correct time complexity?

medium

A. O(n log n)

B. O(n^2)

C. O(n^2 log n)

D. O(n)

Solution

1. Step 1: Analyze the recurrence relation

   T(n) = 2T(n/2) + n^2 means dividing problem into two halves and combining in n^2 time.

2. Step 2: Apply Master Theorem

   Here, a=2, b=2, log_b a = 1, f(n)=n^2 = Ω(n^{1 + ε}) for some ε > 0 (case 3). Thus, time complexity is Θ(n^2) = O(n^2).

3. Final Answer:

   O(n^2) -> Option B

4. Quick Check:

   Master Theorem with f(n)=n^2 gives O(n^2) [OK]

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

Common Mistakes:

• Assuming O(n log n) without checking f(n)
• Ignoring the power of n in f(n)
• Misapplying Master Theorem cases

5. Given the recurrence relation

T(n) = 3T(n/3) + n / log n

Using the Master Theorem, what is the asymptotic time complexity of T(n)?

hard

A. O(n)

B. O(n^{log_3 3})

C. O(n log n)

D. O(n log log n)

Solution

1. Step 1: Identify parameters for Master Theorem

   a=3, b=3, so n^{log_b a} = n^{log_3 3} = n^1 = n.

2. Step 2: Compare f(n) = n / log n with n^{log_b a} = n

   f(n) grows slower than n by a factor of log n. This is a case where f(n) = n / log n = n^{1} / log n.

3. Step 3: Apply Master Theorem case 2 variant

   Since f(n) = n / log n = n^{1} / log n, which is smaller than n^{1} by a log factor, the complexity is O(n log log n).

4. Final Answer:

   O(n log log n) -> Option D

5. Quick Check:

   Master Theorem with f(n) = n / log n gives O(n log log n) [OK]

Hint: Compare f(n) to n^{log_b a} carefully for log factors [OK]

Common Mistakes:

• Ignoring the log factor in f(n)
• Choosing O(n) or O(n log n) incorrectly
• Miscomputing log base