Divide and Conquer Strategy and Recurrence Relations in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Merge Sort Call Count

What is the output of the following code that counts the number of recursive calls in merge sort for an array of size 4?

DSA Python

def merge_sort_count(arr, count=[0]):
    count[0] += 1
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort_count(arr[:mid], count)
    right = merge_sort_count(arr[mid:], count)
    return sorted(left + right)

arr = [4, 3, 2, 1]
count = [0]
merge_sort_count(arr, count)
print(count[0])

A 8

B 7

C 6

D 5

💡 Hint

Count how many times the function is called including base cases.

Merge sort splits the array recursively until single elements. For size 4, calls are: 1 (whole), 2 (two halves), 4 (single elements) totaling 7 calls.

🧠 Conceptual

intermediate

Recurrence Relation for Binary Search

What is the correct recurrence relation for the time complexity of binary search on an array of size n?

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) = T(n/2) + O(n)

💡 Hint

Binary search halves the array each step and does constant work.

Binary search divides the problem size by 2 each step and does constant time work to compare, so T(n) = T(n/2) + O(1).

❓ Predict Output

advanced

Output of Recursive Function with Divide and Conquer

What is the output of this code that calculates the sum of elements using divide and conquer?

DSA Python

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

print(divide_sum([1, 2, 3, 4, 5]))

A 15

B 14

C 10

D Error

💡 Hint

Sum all elements by splitting the array recursively.

The function splits the array recursively and sums left and right parts. The total sum of [1,2,3,4,5] is 15.

🔧 Debug

advanced

Identify the Error in Recurrence Calculation Code

What error does the following code produce when calculating Fibonacci numbers using divide and conquer?

DSA Python

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

print(fib('5'))

A No error, outputs 5

B RecursionError

C ValueError

D TypeError

💡 Hint

Check the type of input passed to the function.

Passing a string '5' causes TypeError when trying to compare or subtract integers.

🧠 Conceptual

expert

Mastering the Master Theorem Case

Given the recurrence T(n) = 4T(n/2) + n^2, what is the time complexity using the Master Theorem?

A O(n^2 log n)

B O(n^3)

C O(n^2)

D O(n log n)

💡 Hint

Compare n^log_b(a) with f(n) where a=4, b=2, f(n)=n^2.

Here, a=4, b=2, so n^log_b(a) = n^2. Since f(n) = n^2, this matches case 2 of Master Theorem, so T(n) = O(n^2 log n).

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)