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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Merge Sort Call Count

Consider the following Go code that counts the number of recursive calls made by a merge sort implementation on an array of size 4. What is the printed output?

DSA Go

package main
import "fmt"
var count int
func mergeSort(arr []int) []int {
    count++
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}
func merge(left, right []int) []int {
    result := []int{}
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    result = append(result, left[i:]...)
    result = append(result, right[j:]...)
    return result
}
func main() {
    arr := []int{4, 3, 2, 1}
    mergeSort(arr)
    fmt.Println(count)
}

A 7

B 8

C 6

D 5

💡 Hint

Count how many times mergeSort is called including the initial call and all recursive calls on subarrays.

Merge sort splits the array into halves recursively until size 1. For size 4, calls are: mergeSort(4 elements), mergeSort(2 elements), mergeSort(1 element) twice, mergeSort(2 elements), mergeSort(1 element) twice. Total calls = 7.

🧠 Conceptual

intermediate

Recurrence Relation for Binary Search

What is the correct recurrence relation for the time complexity T(n) of binary search on a sorted array of size n?

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

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

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

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

💡 Hint

Binary search divides the problem size by half each step and does constant work per step.

Binary search splits the array into half each time and does constant time comparison, so T(n) = T(n/2) + O(1).

❓ Predict Output

advanced

Output of Recursive Function with Divide and Conquer

What is the output of the following Go program?

DSA Go

package main
import "fmt"
func f(n int) int {
    if n <= 1 {
        return 1
    }
    return f(n/2) + f(n/2) + n
}
func main() {
    fmt.Println(f(4))
}

A 10

B 12

C 11

D 9

💡 Hint

Trace the recursive calls and sum their results carefully.

f(1) = 1. f(2) = f(1) + f(1) + 2 = 1 + 1 + 2 = 4. f(4) = f(2) + f(2) + 4 = 4 + 4 + 4 = 12.

🧠 Conceptual

advanced

Master Theorem Case Identification

Given the recurrence T(n) = 3T(n/4) + n, which case of the Master Theorem applies and what is the asymptotic complexity?

A Case 1: T(n) = Θ(n^{log_4 3})

B Case 1: T(n) = Θ(n^{log_3 4})

C Case 3: T(n) = Θ(n)

D Case 2: T(n) = Θ(n log n)

💡 Hint

Compare n with n^{log_b a} where a=3 and b=4.

Here a=3, b=4, log_4 3 ≈ 0.792. f(n)=n = Θ(n^{1}) which is asymptotically larger than n^{log_4 3}. Since f(n) = Θ(n^{log_4 3} * log n), Case 2 applies and T(n) = Θ(n log n).

🔧 Debug

expert

Identify the Error in Recursive Fibonacci Implementation

What error will the following Go code produce when executed?

DSA Go

package main
import "fmt"
func fib(n int) int {
    if n == 0 {
        return 0
    }
    if n == 1 {
        return 1
    }
    return fib(n-1) + fib(n-3)
}
func main() {
    fmt.Println(fib(4))
}

A Stack overflow due to infinite recursion

B Compile-time error: undefined function

C Runtime error: index out of range

D Outputs 3

💡 Hint

Check the recursive calls and base cases carefully.

The function calls fib(n-3) without a base case for n < 0, causing infinite recursion and stack overflow.

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 checking every possible solution one by one

C. Use a single loop to solve the problem directly without recursion

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

Solution

1. Step 1: Understand Divide and Conquer concept

   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 D

4. Quick Check:

   Divide and Conquer = Break, 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 solves without breaking problem
• Mixing with dynamic programming concepts

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(1)

Solution

1. Step 1: Recall Merge Sort process

   Merge Sort divides 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 C

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 merge cost O(n)
• Confusing with other divide and conquer algorithms

3. Consider the following Go function implementing a divide and conquer approach:

func sum(arr []int) int {
    if len(arr) == 1 {
        return arr[0]
    }
    mid := len(arr) / 2
    left := sum(arr[:mid])
    right := sum(arr[mid:])
    return left + right
}

fmt.Println(sum([]int{2, 4, 6, 8}))

What is the output of this code?

medium

A. 20

B. 10

C. 0

D. Runtime error

Solution

1. Step 1: Understand the function behavior

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

2. Step 2: Trace the calls for input [2,4,6,8]

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

3. Final Answer:

   20 -> Option A

4. Quick Check:

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

Hint: Sum all elements by splitting and adding halves [OK]

Common Mistakes:

• Confusing mid index slicing
• Assuming sum returns average
• Thinking it causes runtime error

4. The following Go code is intended to implement a divide and conquer algorithm to find the maximum element in an array. Identify the error:

func max(arr []int) int {
    if len(arr) == 1 {
        return arr[0]
    }
    mid := len(arr) / 2
    left := max(arr[:mid])
    right := max(arr[mid:])
    if left > right {
        return left
    } else {
        return right
    }
}

fmt.Println(max([]int{}))

medium

A. The base case should check for len(arr) == 0

B. The code will panic due to empty slice input

C. The mid calculation is incorrect

D. The comparison between left and right is wrong

Solution

1. Step 1: Analyze base case

   The base case handles only len(arr) == 1, missing handling for empty slices (len(arr) == 0).

2. Step 2: Trace execution on empty input

   len(arr) == 0 skips base case, mid = 0, recurses on arr[:0] and arr[0:], both empty, causing infinite recursion and stack overflow panic.

3. Final Answer:

   The code will panic due to empty slice input -> Option B

4. Quick Check:

   Infinite recursion on empty input causes panic [OK]

Hint: Handle empty input in recursive divide-and-conquer base cases [OK]

Common Mistakes:

• Ignoring empty slice input
• Assuming base case handles empty slice
• Thinking mid calculation 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, so n^{log_b(a)} = 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 A

6. Quick Check:

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

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

Common Mistakes:

• Confusing log base or a and b values
• Choosing wrong Master Theorem case
• Ignoring the extra n factor in recurrence