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

Concept Flow - Divide and Conquer Strategy and Recurrence Relations

Divide Problem

↓

Conquer Subproblems

↓

Combine Results

↓

Final Solution

The problem is split into smaller parts, each part is solved, then results are combined to solve the original problem.

Execution Sample

DSA Java

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

This code divides the problem size by half each time, solves smaller problems recursively, then combines results by adding.

Execution Table

Step	Operation	Parameter n	Recursive Calls	Return Value	Explanation
1	Call divideAndConquer	8	Calls divideAndConquer(4)	-	Start with n=8, divide into half=4
2	Call divideAndConquer	4	Calls divideAndConquer(2)	-	Divide 4 into half=2
3	Call divideAndConquer	2	Calls divideAndConquer(1)	-	Divide 2 into half=1
4	Call divideAndConquer	1	Base case reached	1	n=1 base case returns 1
5	Return from divideAndConquer(1)	1	-	1	Return 1 to caller with n=2
6	Calculate return for n=2	2	-	2	half + half = 1 + 1 = 2
7	Return from divideAndConquer(2)	2	-	2	Return 2 to caller with n=4
8	Calculate return for n=4	4	-	4	half + half = 2 + 2 = 4
9	Return from divideAndConquer(4)	4	-	4	Return 4 to caller with n=8
10	Calculate return for n=8	8	-	8	half + half = 4 + 4 = 8
11	Return from divideAndConquer(8)	8	-	8	Final return value 8

💡 Recursion stops when n reaches 1, the base case.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 6	After Step 8	Final
n	8	8	4	2	1	2	4	8
half	-	-	-	-	-	1	2	4
Return Value	-	-	-	-	1	2	4	8

Key Moments - 3 Insights

Why does the recursion stop when n equals 1?

Because the base case is defined at n=1 (see execution_table step 4), which returns a fixed value to prevent infinite recursion.

How does the problem size reduce in each recursive call?

At each step, n is divided by 2 (see execution_table steps 1-3), reducing the problem size until the base case is reached.

Why do we add half + half when combining results?

Because the problem is split into two equal parts, and their results are combined by addition (see steps 6, 8, 10).

Visual Quiz - 3 Questions

Look at the execution_table, what is the return value when n is 4?

A 2

B 1

C 4

D 8

💡 Hint

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

At which step does the recursion reach the base case?

A Step 3

B Step 4

C Step 6

D Step 10

💡 Hint

Look for the step where 'Base case reached' is mentioned in the 'Operation' column.

If the problem size n started at 16 instead of 8, how many recursive calls would happen before reaching the base case?

A 4

B 3

C 5

D 2

💡 Hint

Each recursive call divides n by 2 until n=1; count how many times 16 divides by 2 to reach 1.

Concept Snapshot

Divide and Conquer splits a problem into smaller parts,
solves each recursively, then combines results.
Recurrence relations describe the time cost.
Base case stops recursion.
Example: T(n) = T(n/2) + O(1).
Used in sorting, searching, and more.

Full Transcript

Divide and Conquer is a strategy where a problem is divided into smaller subproblems, each solved recursively, and their results combined to form the final solution. The recursion stops at a base case, usually when the problem size is minimal. The example code divides the input n by 2 each time, calls itself recursively, and combines results by adding. The execution table shows each recursive call, the parameter n, and the return values. The variable tracker follows how n and the return values change. Key moments clarify why recursion stops at n=1, how problem size reduces, and why results are combined by addition. The visual quiz tests understanding of return values, base case step, and recursion depth for larger inputs. The concept snapshot summarizes the strategy and its recurrence relation.

Practice

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

easy

A. Store all intermediate results to avoid repeated calculations

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

C. Use a single loop to iterate through all elements

D. Break the problem into smaller subproblems, solve them independently, then combine results

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 subproblems

   After solving smaller parts, 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 D

4. Quick Check:

   Divide and conquer = split, solve, combine [OK]

Hint: Divide big problem 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) = T(n/2) + O(1)

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

C. T(n) = T(n-1) + 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, 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)
• Ignoring the merge cost O(n)
• Confusing with quicksort recurrence

3. What is the output of the following Java method that uses divide and conquer?

public static int sumArray(int[] arr, int start, int end) {
    if (start == end) return arr[start];
    int mid = (start + end) / 2;
    return sumArray(arr, start, mid) + sumArray(arr, mid + 1, end);
}

public static void main(String[] args) {
    int[] nums = {2, 4, 6, 8};
    System.out.println(sumArray(nums, 0, nums.length - 1));
}

medium

A. 20

B. 10

C. 0

D. Compilation error

Solution

1. Step 1: Understand the method's logic

   The method splits the array into halves recursively and sums elements.

2. Step 2: Calculate sum of array elements

   Sum of {2,4,6,8} = 2+4+6+8 = 20.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Sum of array = 20 [OK]

Hint: Divide array, sum halves, add results [OK]

Common Mistakes:

• Confusing mid calculation causing infinite recursion
• Forgetting to include last element
• Assuming method returns partial sums

4. Identify the error in the following recurrence relation code snippet for a divide and conquer algorithm:

int divideConquer(int n) {
    if (n == 1) return 1;
    int result = divideConquer(n / 2) + divideConquer(n / 2);
    return result + n;
}

medium

A. The base case should be n == 0 instead of n == 1

B. No error, code is correct

C. The function calls divideConquer(n / 2) twice causing redundant work

D. The addition of n should be outside the return statement

Solution

1. Step 1: Analyze recursive calls

   The function calls divideConquer(n/2) twice separately, repeating work.

2. Step 2: Identify redundancy

   Calling the same function twice with same argument duplicates effort, inefficient.

3. Final Answer:

   The function calls divideConquer(n / 2) twice causing redundant work -> Option C

4. Quick Check:

   Repeated calls with same input cause redundancy [OK]

Hint: Avoid duplicate recursive calls with same parameters [OK]

Common Mistakes:

• Thinking base case is wrong
• Ignoring duplicate calls
• Assuming addition placement causes error

5. Given the recurrence relation T(n) = 3T(n/3) + n, which of the following is the correct time complexity using the Master Theorem?

hard

A. O(n log n)

B. O(n^2)

C. O(n)

D. O(log n)

Solution

1. Step 1: Identify parameters for Master Theorem

   Here, a=3, b=3, f(n)=n.

2. Step 2: Calculate log_b(a)

   log_3(3) = 1.

3. Step 3: 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)}).

4. Step 4: Apply Master Theorem case 2

   Time complexity T(n) = Theta(n log n).

5. Final Answer:

   O(n log n) -> Option A

6. Quick Check:

   Master theorem case 2 = n log n [OK]

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

Common Mistakes:

• Confusing log base or value
• Choosing wrong Master theorem case
• Ignoring the additive term n