Divide and Conquer Strategy and Recurrence Relations in DSA C

Mental Model

Break a big problem into smaller similar problems, solve each one, then combine results.

Analogy: Like cutting a big cake into smaller pieces, eating each piece, then feeling full from the whole cake.

Big Problem
   ↓
+----------+
| Divide   |
+----------+
   ↓ ↓ ↓
Small Problems
   ↓ ↓ ↓
+----------+
| Conquer  |
+----------+
   ↓
Combine Results
   ↓
Solution

Dry Run Walkthrough

Input: Sort array: [4, 2, 7, 1]

Goal: Sort the array using divide and conquer by splitting, sorting, and merging

Step 1: Divide array into two halves: [4, 2] and [7, 1]

[4, 2, 7, 1]
Split -> [4, 2] and [7, 1]

Why: We break the big problem into smaller parts to handle easily

Step 2: Divide [4, 2] into [4] and [2]

[4] and [2]
Each is a single element

Why: Single elements are already sorted, base case reached

Step 3: Merge [4] and [2] into sorted [2, 4]

[2, 4]

Why: Combine sorted parts to get bigger sorted array

Step 4: Divide [7, 1] into [7] and [1]

[7] and [1]

Why: Again, base case with single elements

Step 5: Merge [7] and [1] into sorted [1, 7]

[1, 7]

Why: Combine sorted parts

Step 6: Merge sorted halves [2, 4] and [1, 7] into [1, 2, 4, 7]

[1, 2, 4, 7]

Why: Final combine step to get fully sorted array

Result:

[1, 2, 4, 7] -- sorted array

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    free(L);
    free(R);
}

void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // find middle
        mergeSort(arr, left, mid); // sort left half
        mergeSort(arr, mid + 1, right); // sort right half
        merge(arr, left, mid, right); // merge sorted halves
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d", arr[i]);
        if (i < size - 1) printf(", ");
    }
    printf("\n");
}

int main() {
    int arr[] = {4, 2, 7, 1};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, size);

    mergeSort(arr, 0, size - 1);

    printf("Sorted array: ");
    printArray(arr, size);

    return 0;
}

int mid = left + (right - left) / 2; // find middle

divide problem into two halves

mergeSort(arr, left, mid); // sort left half

recursively conquer left half

mergeSort(arr, mid + 1, right); // sort right half

recursively conquer right half

merge(arr, left, mid, right); // merge sorted halves

combine sorted halves into one sorted array

while (i < n1 && j < n2) { ... }

merge elements from two halves in order

Output

Original array: 4, 2, 7, 1

Sorted array: 1, 2, 4, 7

Complexity Analysis

Time: O(n log n) because the array is divided into halves log n times and merging takes O(n) each time

Space: O(n) because temporary arrays are used during merging

vs Alternative: Naive sorting like bubble sort is O(n^2), much slower for large n; divide and conquer is more efficient

Edge Cases

Empty array

No sorting needed, function returns immediately

DSA C

if (left < right) {

Single element array

Already sorted, recursion stops immediately

DSA C

if (left < right) {

Array with duplicate elements

Duplicates are handled correctly and appear in sorted order

DSA C

if (L[i] <= R[j]) {

When to Use This Pattern

When a problem can be split into smaller similar problems and combined, use divide and conquer to solve efficiently.

Common Mistakes

Mistake: Not handling base case properly causing infinite recursion
Fix: Add condition to stop recursion when subarray size is 1 or 0 (if left < right)

Mistake: Incorrect merging causing unsorted output
Fix: Carefully compare elements from both halves and copy in sorted order

Summary

It breaks a problem into smaller parts, solves each, then combines results.

Use it when a problem can be divided into similar subproblems.

The key is to divide, conquer recursively, and then merge results.

Practice

1. What is the main idea behind the Divide and Conquer strategy in algorithms?

easy

A. Use a single loop to solve the problem iteratively

B. Solve the problem by trying all possible solutions one by one

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

D. Store all intermediate results to avoid repeated calculations

Solution

1. Step 1: Understand Divide and Conquer approach

   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 C

4. Quick Check:

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

Hint: Divide big problem into parts, solve parts, 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 recurrence relation for the Merge Sort algorithm on an array of size n?

easy

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

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

C. T(n) = T(n/2) + 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 recursively, then merges in O(n) time.

2. Step 2: Write recurrence relation

   It calls itself twice on size n/2 plus linear merge step, so T(n) = 2T(n/2) + O(n).

3. Final Answer:

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

4. Quick Check:

   Merge Sort recurrence = 2 halves + merge O(n) [OK]

Hint: Two halves plus linear merge step means 2T(n/2)+n [OK]

Common Mistakes:

• Using T(n-1) instead of T(n/2)
• Ignoring the merge step cost
• Confusing with quicksort recurrence

3. Consider the following C code implementing a divide and conquer function:

int func(int n) {
    if (n <= 1) return 1;
    return func(n/2) + func(n/2) + n;
}

What is the time complexity T(n) of this function?

medium

A. O(n^2)

B. O(n)

C. O(log n)

D. O(n log n)

Solution

1. Step 1: Identify recurrence relation

   The function calls itself twice on n/2 plus does O(n) work, so T(n) = 2T(n/2) + n.

2. Step 2: Solve recurrence using Master Theorem

   For T(n) = 2T(n/2) + n, the solution is O(n log n).

3. Final Answer:

   O(n log n) -> Option D

4. Quick Check:

   2 calls on half + linear work = n log n [OK]

Hint: Two halves plus linear work means n log n time [OK]

Common Mistakes:

• Thinking it is O(n) by ignoring recursive calls
• Confusing with O(log n) for single call
• Mistaking it for quadratic O(n^2)

4. The following recurrence relation is given:

T(n) = 3T(n/3) + n^2

There is a mistake in the code implementing this recurrence. Which fix will correct the recurrence to match the intended divide and conquer approach?

medium

A. Change the recursive calls to 3T(n/3) and keep n^2 as extra work

B. Change the extra work from n^2 to n log n

C. Change the recursive calls to T(n-1) and keep n^2

D. Change the recursive calls to 2T(n/2) and keep n^2

Solution

1. Step 1: Understand the recurrence meaning

   3T(n/3) means dividing problem into 3 equal parts recursively, plus n^2 extra work.

2. Step 2: Fix code to match recurrence

   Ensure code calls itself 3 times on n/3 size and does n^2 work outside recursion.

3. Final Answer:

   Change the recursive calls to 3T(n/3) and keep n^2 as extra work -> Option A

4. Quick Check:

   3 recursive calls on n/3 + n^2 work = 3T(n/3)+n^2 [OK]

Hint: Match recursive calls count and size to recurrence exactly [OK]

Common Mistakes:

• Changing extra work without fixing recursive calls
• Using wrong subproblem size like n-1
• Reducing calls to 2 instead of 3

5. You have a problem of size n that you divide into 4 subproblems each of size n/2. The extra work done outside the recursive calls is O(n^2). What is the time complexity T(n) of this divide and conquer algorithm?

hard

A. O(n^2 log n)

B. O(n^3)

C. O(n^2)

D. O(n log n)

Solution

1. Step 1: Write the recurrence relation

   Since there are 4 subproblems each size n/2 and extra work n^2, T(n) = 4T(n/2) + n^2.

2. Step 2: Apply Master Theorem

   Here, a=4, b=2, f(n)=n^2. Calculate log_b(a) = log_2(4) = 2. Since f(n) = Theta(n^2), it matches n^{log_b(a)}.

3. Step 3: Determine complexity

   By Master Theorem case 2, T(n) = Theta(n^2 log n).

4. Final Answer:

   O(n^2 log n) -> Option A

5. Quick Check:

   4 calls on half + n^2 work = n^2 log n [OK]

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

Common Mistakes:

• Ignoring the log factor in complexity
• Confusing number of subproblems with size
• Mistaking it for cubic or linear complexity