Divide and Conquer Strategy and Recurrence Relations in DSA Java - Build from Scratch

Divide and Conquer Strategy and Recurrence Relations

📖 Scenario: Imagine you have a large list of numbers representing daily sales in a store. You want to find the maximum sale amount efficiently by breaking the problem into smaller parts.

🎯 Goal: Build a Java program that uses the divide and conquer strategy to find the maximum number in an array. You will also see how the problem breaks down into smaller parts and how the recurrence relation describes the process.

📋 What You'll Learn

Create an integer array called sales with the exact values: {12, 45, 7, 89, 34, 23, 56, 78}

Create an integer variable called n that stores the length of the sales array

Write a recursive method called findMax that takes the array, a start index, and an end index, and returns the maximum value using divide and conquer

Print the maximum sale value found by calling findMax on the entire array

💡 Why This Matters

🌍 Real World

Finding maximum or minimum values quickly in large datasets is common in sales analysis, stock prices, and sensor data.

💼 Career

Understanding divide and conquer helps in optimizing algorithms and solving complex problems efficiently in software development.

1

Create the sales data array

Create an integer array called sales with the exact values {12, 45, 7, 89, 34, 23, 56, 78}.

DSA Java

// Your code here

Hint

Use int[] sales = {12, 45, 7, 89, 34, 23, 56, 78}; to create the array.

2

Add the length variable

Create an integer variable called n that stores the length of the sales array.

DSA Java

public class Main {
    public static void main(String[] args) {
        int[] sales = {12, 45, 7, 89, 34, 23, 56, 78};
        // Your code here
    }
}

Hint

Use int n = sales.length; to get the array length.

3

Write the recursive findMax method

Write a recursive method called findMax inside the Main class that takes an integer array arr, a start index start, and an end index end. It should return the maximum value in that range using divide and conquer strategy.

DSA Java

public class Main {
    public static void main(String[] args) {
        int[] sales = {12, 45, 7, 89, 34, 23, 56, 78};
        int n = sales.length;
    }

    // Your code here
}

Hint

Use the base case when start == end to return the single element. Otherwise, split the array into two halves and find the max in each half recursively.

4

Print the maximum sale value

Print the maximum sale value by calling findMax on the entire sales array using System.out.println.

DSA Java

public class Main {
    public static void main(String[] args) {
        int[] sales = {12, 45, 7, 89, 34, 23, 56, 78};
        int n = sales.length;
        // Your code here
    }

    public static int findMax(int[] arr, int start, int end) {
        if (start == end) {
            return arr[start];
        }
        int mid = (start + end) / 2;
        int maxLeft = findMax(arr, start, mid);
        int maxRight = findMax(arr, mid + 1, end);
        return Math.max(maxLeft, maxRight);
    }
}

Hint

Call findMax(sales, 0, n - 1) and print the result using System.out.println.

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