Exercise 4.1.3

Implement both the brute-force and recursive algorithms for the maximum-subarray problem on your own computer. What problem size $n_0$ gives the crossover point at which the recursive algorithm beats the brute-force algorithm? Then, change the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than $n_0$. Does that change the crossover point?

On my computer, $n_0$ is 37.

If the algorithm is modified to used divide in conquer when $n \geq 37$ and the brute-force approach when $n$ is less, the performance at the crossover point almost doubles. The performance at $n_0 - 1$ stays the same, though (or even gets worse, because of the added overhead).

What I find interesting is that if we set $n_0 = 20$ and used the mixed approach to sort $40$ elements, it is still faster than both.

C runner output

37 elements, 10000 times...
brute-force        = 0.018271
divide-and-conquer = 0.009907
mixed              = 0.008405
=============================
7400 elements, 1 time...
brute-force        = 0.044259
divide-and-conquer = 0.000434
mixed              = 0.000388

C code

#include <limits.h>

#define CROSSOVER_POINT 37

// A struct to represent the tuple

typedef struct {
    unsigned left;
    unsigned right;
    int sum;
} max_subarray;

// The brute force approach

max_subarray find_maximum_subarray_brute(int A[], unsigned low, unsigned high) {
    max_subarray result = {0, 0, INT_MIN};

    for (int i = low; i < high; i++) {
        int current_sum = 0;
        for (int j = i; j < high; j++) {
            current_sum += A[j];
            if (result.sum < current_sum) {
                result.left = i;
                result.right = j + 1;
                result.sum = current_sum;
            }
        }
    }

    return result;
}

// The divide-and-conquer solution

max_subarray find_max_crossing_subarray(int A[], unsigned low, unsigned mid, unsigned high) {
    max_subarray result = {-1, -1, 0};
    int sum = 0,
        left_sum = INT_MIN,
        right_sum = INT_MIN;

    for (int i = mid - 1; i >= (int) low; i--) {
        sum += A[i];
        if (sum > left_sum) {
            left_sum = sum;
            result.left = i;
        }
    }

    sum = 0;

    for (int j = mid; j < high; j++) {
        sum += A[j];
        if (sum > right_sum) {
            right_sum = sum;
            result.right = j + 1;
        }
    }

    result.sum = left_sum + right_sum;
    return result;
}

max_subarray find_maximum_subarray(int A[], unsigned low, unsigned high) {
    if (high == low + 1) {
        max_subarray result = {low, high, A[low]};
        return result;
    } else {
        unsigned mid = (low + high) / 2;
        max_subarray left = find_maximum_subarray(A, low, mid);
        max_subarray right = find_maximum_subarray(A, mid, high);
        max_subarray cross = find_max_crossing_subarray(A, low, mid, high);

        if (left.sum >= right.sum && left.sum >= cross.sum) {
            return left;
        } else if (right.sum >= left.sum && right.sum >= cross.sum) {
            return right;
        } else {
            return cross;
        }
    }
}

// The mixed algorithm

max_subarray find_maximum_subarray_mixed(int A[], unsigned low, unsigned high) {
    if (high - low < CROSSOVER_POINT) {
        return find_maximum_subarray_brute(A, low, high);
    } else {
        unsigned mid = (low + high) / 2;
        max_subarray left = find_maximum_subarray_mixed(A, low, mid);
        max_subarray right = find_maximum_subarray_mixed(A, mid, high);
        max_subarray cross = find_max_crossing_subarray(A, low, mid, high);

        if (left.sum >= right.sum && left.sum >= cross.sum) {
            return left;
        } else if (right.sum >= left.sum && right.sum >= cross.sum) {
            return right;
        } else {
            return cross;
        }
    }
}