Find Maximum Subarray Divide and Conquer in DSA C - Time & Space Complexity

Time Complexity: Find Maximum Subarray Divide and Conquer

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to find the maximum subarray grows as the input array gets bigger.

Specifically, how the divide and conquer method affects the work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int maxCrossingSum(int arr[], int left, int mid, int right) {
    int sum = 0, left_sum = INT_MIN;
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > left_sum) left_sum = sum;
    }
    sum = 0;
    int right_sum = INT_MIN;
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > right_sum) right_sum = sum;
    }
    return left_sum + right_sum;
}

int maxSubArraySum(int arr[], int left, int right) {
    if (left == right) return arr[left];
    int mid = (left + right) / 2;
    int left_max = maxSubArraySum(arr, left, mid);
    int right_max = maxSubArraySum(arr, mid + 1, right);
    int cross_max = maxCrossingSum(arr, left, mid, right);
    return (left_max > right_max) ? (left_max > cross_max ? left_max : cross_max) : (right_max > cross_max ? right_max : cross_max);
}
    

This code finds the maximum sum of a subarray using divide and conquer by splitting the array and combining results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls splitting the array into halves.
• How many times: Each level splits the array into two parts, so recursion depth is about log n.
• Secondary operation: The maxCrossingSum function loops over parts of the array crossing the middle.
• How many times: At each recursion level, maxCrossingSum scans parts of the array once, totaling n work per level.

How Execution Grows With Input

At each level, the total work scanning the array is about n, and the number of levels is about log n.

Input Size (n)	Approx. Operations
10	About 10 * 4 = 40
100	About 100 * 7 = 700
1000	About 1000 * 10 = 10,000

Pattern observation: Operations grow roughly by n times log n, meaning work grows faster than linear but slower than quadratic.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a bit faster than the size of the input, but not as fast as checking every pair.

Common Mistake

[X] Wrong: "Since the array is split in half each time, the time complexity is O(log n)."

[OK] Correct: Although the array splits reduce the problem size, the crossing sum loops over parts of the array at each level, adding up to n work per level, so total work is more than just log n.

Interview Connect

Understanding this divide and conquer approach helps you see how breaking problems down and combining results affects performance, a key skill in many coding challenges.

Self-Check

"What if we replaced the maxCrossingSum function with a method that scans the entire array each time? How would the time complexity change?"