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

Divide and Conquer Strategy and Recurrence Relations

📖 Scenario: Imagine you have a large list of numbers and you want to find the maximum number quickly. Instead of checking each number one by one, you can split the list into smaller parts, find the maximum in each part, and then combine the results. This is called the divide and conquer strategy.

🎯 Goal: Build a simple C++ program that uses divide and conquer to find the maximum number in a list. You will also see how the problem breaks down into smaller parts and how the results combine, which relates to recurrence relations.

📋 What You'll Learn

Create an array of integers with exact values

Create a function to find the maximum using divide and conquer

Use recursion to split the array into halves

Print the maximum number found

💡 Why This Matters

🌍 Real World

Divide and conquer is used in many algorithms like sorting, searching, and solving complex problems by breaking them into smaller parts.

💼 Career

Understanding divide and conquer helps in writing efficient code and solving problems in software development, data analysis, and algorithm design.

1

Create the array of integers

Create an integer array called numbers with these exact values: 3, 5, 1, 8, 2, 9, 4.

DSA C++

// Your code here

Hint

Use the syntax int numbers[] = {values}; to create the array.

2

Add the divide and conquer function declaration

Add a function declaration called findMax that takes three parameters: an integer array arr, an integer start, and an integer end. The function will return an integer.

DSA C++

#include 

// Declare the function findMax here

int main() {
    int numbers[] = {3, 5, 1, 8, 2, 9, 4};
    return 0;
}

Hint

Write the function declaration before main().

3

Implement the divide and conquer logic in findMax

Implement the function findMax to find the maximum number in the array arr between indices start and end using divide and conquer. If start equals end, return arr[start]. Otherwise, find the middle index, call findMax recursively on the left and right halves, and return the larger of the two results.

DSA C++

#include 

int findMax(int arr[], int start, int end) {
    // Your code here
}

int main() {
    int numbers[] = {3, 5, 1, 8, 2, 9, 4};
    return 0;
}

Hint

Use recursion to split the array and compare the maximums from each half.

4

Call findMax and print the result

In main(), call findMax with numbers, 0 as start, and 6 as end. Store the result in an integer variable called maxValue. Then print maxValue using std::cout.

DSA C++

#include 

int findMax(int arr[], int start, int end) {
    if (start == end) {
        return arr[start];
    }
    int mid = (start + end) / 2;
    int leftMax = findMax(arr, start, mid);
    int rightMax = findMax(arr, mid + 1, end);
    return (leftMax > rightMax) ? leftMax : rightMax;
}

int main() {
    int numbers[] = {3, 5, 1, 8, 2, 9, 4};
    // Your code here
}

Hint

Call findMax(numbers, 0, 6), save it to maxValue, then print maxValue.

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 iterate through all elements

D. Store all intermediate results to avoid repeated calculations

Solution

1. Step 1: Understand Divide and Conquer concept

   Divide and conquer splits a problem into smaller parts, solves each part, then merges results.

2. Step 2: Compare options

   Break the problem into smaller subproblems, solve them independently, then combine results correctly describes this process. Options B, C, and D describe other strategies like brute force or dynamic programming.

3. Final Answer:

   Break the problem into smaller subproblems, solve them independently, then combine results -> Option A

4. Quick Check:

   Divide and Conquer = Break, Solve, Combine [OK]

Hint: Divide and conquer means split, solve, then merge results [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) = 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(log n)

Solution

1. Step 1: Recall Merge Sort recurrence

   Merge Sort divides array into two halves, sorts each half (2T(n/2)) and merges in O(n).

2. Step 2: Match with options

   T(n) = 2T(n/2) + O(n) matches 2T(n/2) + O(n). Others describe different algorithms or complexities.

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 and merges in linear time [OK]

Common Mistakes:

• Using T(n-1) instead of T(n/2)
• Confusing merge cost with recursive calls
• Choosing quadratic terms incorrectly

3. What is the output of the following C++ function call:

int count = 0;
int func(int n) {
  if (n <= 1) return 1;
  count++;
  return func(n/2) + func(n/2);
}
int main() {
  func(8);
  std::cout << count;
  return 0;
}

medium

A. 15

B. 7

C. 8

D. 6

Solution

1. Step 1: Understand recursion calls and count increments

   func(8) calls func(4) twice, each func(4) calls func(2) twice, and so on until n <= 1.

2. Step 2: Count increments at each call

   Count increments at each non-base call. The recursion tree has 15 non-base calls (all calls except those where n <= 1). Thus, count increments 15 times.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Count increments for each non-base call = 15 [OK]

Hint: Count increments at each non-base recursive call [OK]

Common Mistakes:

• Counting base case calls
• Not doubling calls for each recursion
• Miscounting due to integer division

4. Identify the error in the following recurrence relation and fix it:

T(n) = 2T(n/2) + n^2 for n > 1
T(1) = 1

What is the correct time complexity?

medium

A. O(n log n)

B. O(n^2)

C. O(n^2 log n)

D. O(n)

Solution

1. Step 1: Analyze the recurrence relation

   T(n) = 2T(n/2) + n^2 means dividing problem into two halves and combining in n^2 time.

2. Step 2: Apply Master Theorem

   Here, a=2, b=2, log_b a = 1, f(n)=n^2 = Ω(n^{1 + ε}) for some ε > 0 (case 3). Thus, time complexity is Θ(n^2) = O(n^2).

3. Final Answer:

   O(n^2) -> Option B

4. Quick Check:

   Master Theorem with f(n)=n^2 gives O(n^2) [OK]

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

Common Mistakes:

• Assuming O(n log n) without checking f(n)
• Ignoring the power of n in f(n)
• Misapplying Master Theorem cases

5. Given the recurrence relation

T(n) = 3T(n/3) + n / log n

Using the Master Theorem, what is the asymptotic time complexity of T(n)?

hard

A. O(n)

B. O(n^{log_3 3})

C. O(n log n)

D. O(n log log n)

Solution

1. Step 1: Identify parameters for Master Theorem

   a=3, b=3, so n^{log_b a} = n^{log_3 3} = n^1 = n.

2. Step 2: Compare f(n) = n / log n with n^{log_b a} = n

   f(n) grows slower than n by a factor of log n. This is a case where f(n) = n / log n = n^{1} / log n.

3. Step 3: Apply Master Theorem case 2 variant

   Since f(n) = n / log n = n^{1} / log n, which is smaller than n^{1} by a log factor, the complexity is O(n log log n).

4. Final Answer:

   O(n log log n) -> Option D

5. Quick Check:

   Master Theorem with f(n) = n / log n gives O(n log log n) [OK]

Hint: Compare f(n) to n^{log_b a} carefully for log factors [OK]

Common Mistakes:

• Ignoring the log factor in f(n)
• Choosing O(n) or O(n log n) incorrectly
• Miscomputing log base