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

Concept Flow - Divide and Conquer Strategy and Recurrence Relations

Divide Problem

↓

Divide into Subproblems

↓

Conquer: Solve Subproblems Recursively

↓

Combine Subproblem Solutions

↓

Final Solution

↓

Analyze Recurrence Relation

↓

Solve Recurrence for Complexity

The problem is split into smaller parts, solved recursively, then combined. The time is analyzed using recurrence relations.

Execution Sample

DSA Python

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr)//2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

This code divides an array into halves recursively and merges sorted halves, demonstrating divide and conquer.

Execution Table

Step	Operation	Subproblem Size	Recursion Depth	Action	Visual State
1	Divide array of size 8	8	0	Split into two arrays of size 4	[8]
2	Divide left half size 4	4	1	Split into two arrays of size 2	[4,4]
3	Divide left-left half size 2	2	2	Split into two arrays of size 1	[2,2,4]
4	Base case reached size 1	1	3	Return single element array	[1,2,2,4]
5	Base case reached size 1	1	3	Return single element array	[1,2,2,4]
6	Conquer: merge two size 1 arrays	2	2	Merge to sorted array size 2	[2,4]
7	Divide right half size 2	2	2	Split into two arrays of size 1	[2,4]
8	Base case reached size 1	1	3	Return single element array	[1,2,4]
9	Base case reached size 1	1	3	Return single element array	[1,2,4]
10	Conquer: merge two size 1 arrays	2	2	Merge to sorted array size 2	[2,4]
11	Conquer: merge two size 2 arrays	4	1	Merge to sorted array size 4	[4]
12	Divide right half size 4	4	1	Split into two arrays of size 2	[4]
13	Divide right-left half size 2	2	2	Split into two arrays of size 1	[4]
14	Base case reached size 1	1	3	Return single element array	[4]
15	Base case reached size 1	1	3	Return single element array	[4]
16	Conquer: merge two size 1 arrays	2	2	Merge to sorted array size 2	[4]
17	Divide right-right half size 2	2	2	Split into two arrays of size 1	[4]
18	Base case reached size 1	1	3	Return single element array	[4]
19	Base case reached size 1	1	3	Return single element array	[4]
20	Conquer: merge two size 1 arrays	2	2	Merge to sorted array size 2	[4]
21	Conquer: merge two size 2 arrays	4	1	Merge to sorted array size 4	[4]
22	Conquer: merge two size 4 arrays	8	0	Merge to sorted array size 8	[8]
23	Recurrence: T(n) = 2T(n/2) + O(n)	-	-	Analyze time complexity	O(n log n)
24	Solve recurrence	-	-	Final time complexity is O(n log n)	O(n log n)

💡 All subproblems reduced to size 1, merged back, recurrence solved.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	After Step 11	After Step 22	Final
arr size	8	8	4	2	2	4	8	8
recursion depth	0	1	2	3	2	1	0	0
subproblem count	1	2	4	8	8	4	2	1

Key Moments - 3 Insights

Why do we stop dividing when subproblem size is 1?

Because at size 1, the array is already sorted (base case). See execution_table rows 4,5,8,9,14,15,18,19 where recursion stops.

How does the recursion depth relate to subproblem size?

Each recursion level halves the problem size, so depth increases as size decreases. See variable_tracker 'recursion depth' increasing as 'arr size' halves.

Why is the recurrence relation T(n) = 2T(n/2) + O(n)?

Because the problem splits into two halves (2T(n/2)) and merging takes linear time O(n). See execution_table step 23.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the subproblem size being merged?

A 1

B 2

C 4

D 8

💡 Hint

Check the 'Subproblem Size' column at step 6 in execution_table.

At which recursion depth does the base case occur?

A 0

B 1

C 3

D 2

💡 Hint

Look at 'Recursion Depth' column in execution_table rows where 'Base case reached size 1' occurs.

If the array size doubles, how does the recursion depth change?

A Increases by 1

B Doubles

C Decreases by 1

D Remains the same

💡 Hint

Refer to variable_tracker showing recursion depth vs array size.

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).
Solving recurrence gives time complexity.
Example: Merge Sort uses T(n) = 2T(n/2) + O(n) → O(n log n).

Full Transcript

Divide and Conquer breaks a problem into smaller subproblems, solves them recursively, and combines their solutions. The process continues until subproblems are simple enough to solve directly, often size one. The time taken is expressed as a recurrence relation, like T(n) = 2T(n/2) + O(n) for merge sort. Solving this recurrence shows the overall time complexity, here O(n log n). The execution table traces dividing the array, reaching base cases, merging back, and analyzing the recurrence. Variables like recursion depth and subproblem size change predictably. Key moments clarify why recursion stops at size one, how depth relates to size, and why the recurrence is formed as it is.

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 solve the problem iteratively

D. Store all intermediate results to avoid repeated calculations

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 A

4. Quick Check:

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

Hint: Divide big problem into smaller parts, solve, 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 syntax for the recurrence relation of Merge Sort?

easy

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

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

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

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

Solution

1. Step 1: Recall Merge Sort recurrence

   Merge Sort splits array into two halves, sorts each half, then merges in linear time.

2. Step 2: Write recurrence relation

   It calls itself twice on half size (2T(n/2)) plus O(n) for merging.

3. Final Answer:

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

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)
• Confusing merge cost as O(n^2)
• Choosing wrong number of recursive calls

3. What is the output of this Python function that uses divide and conquer to compute sum of a list?

def sum_list(arr):
    if len(arr) == 1:
        return arr[0]
    mid = len(arr) // 2
    left_sum = sum_list(arr[:mid])
    right_sum = sum_list(arr[mid:])
    return left_sum + right_sum

print(sum_list([2, 4, 6, 8]))

medium

A. 16

B. 20

C. Error

D. 10

Solution

1. Step 1: Trace recursive calls

   List splits into [2,4] and [6,8], then further into single elements.

2. Step 2: Calculate sums bottom-up

   Sum of [2,4] = 6, sum of [6,8] = 14, total = 6 + 14 = 20.

3. Final Answer:

   20 -> Option B

4. Quick Check:

   2+4+6+8 = 20 [OK]

Hint: Sum divides list, sums parts, then adds [OK]

Common Mistakes:

• Confusing mid index slicing
• Returning partial sums incorrectly
• Forgetting base case for single element

4. Find the error in this divide and conquer function to find maximum element in a list:

def max_element(arr):
    if len(arr) == 1:
        return arr[0]
    mid = len(arr) // 2
    left_max = max_element(arr[:mid])
    right_max = max_element(arr[mid:])
    if left_max > right_max:
        return left_max
    else:
        return arr[right_max]

medium

A. Function should use iteration instead of recursion

B. Base case missing for empty list

C. Mid calculation should be mid = len(arr) // 3

D. Incorrect return statement: should return right_max, not arr[right_max]

Solution

1. Step 1: Check return statements

   Left max returns value correctly, right max returns index incorrectly by arr[right_max].

2. Step 2: Fix return for right max comparison

   Should return right_max directly, not arr[right_max], because right_max is already a value.

3. Final Answer:

   Incorrect return statement: should return right_max, not arr[right_max] -> Option D

4. Quick Check:

   Return max values, not index or wrong element [OK]

Hint: Return max values, not arr[value] [OK]

Common Mistakes:

• Returning element by index instead of value
• Wrong slicing causing infinite recursion
• Ignoring base case for single element

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

hard

A. O(n)

B. O(n^2)

C. O(n log 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 n^log_b(a)

   log_3(3) = 1, so n^1 = n.

3. Step 3: Compare f(n) with n^log_b(a)

   f(n) = n matches n^log_b(a) = n, so case 2 applies.

4. Step 4: Apply Master Theorem case 2

   Time complexity is O(n log n).

5. Final Answer:

   O(n log n) -> Option C

6. Quick Check:

   Master Theorem case 2 = O(n log n) [OK]

Hint: Compare f(n) to n^log_b(a) for Master Theorem [OK]

Common Mistakes:

• Confusing log base or value
• Choosing wrong Master Theorem case
• Ignoring the additive term f(n)