Find Maximum Subarray Divide and Conquer in DSA Typescript - 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.

How does the divide and conquer method affect the work done compared to just checking every subarray?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function maxSubArray(arr: number[], left: number, right: number): number {
  if (left === right) return arr[left];
  const mid = Math.floor((left + right) / 2);
  const leftMax = maxSubArray(arr, left, mid);
  const rightMax = maxSubArray(arr, mid + 1, right);
  const crossMax = maxCrossingSubArray(arr, left, mid, right);
  return Math.max(leftMax, rightMax, crossMax);
}

function maxCrossingSubArray(arr: number[], left: number, mid: number, right: number): number {
  let leftSum = -Infinity, sum = 0;
  for (let i = mid; i >= left; i--) {
    sum += arr[i];
    if (sum > leftSum) leftSum = sum;
  }
  let rightSum = -Infinity;
  sum = 0;
  for (let i = mid + 1; i <= right; i++) {
    sum += arr[i];
    if (sum > rightSum) rightSum = sum;
  }
  return leftSum + rightSum;
}
    

This code finds the maximum sum of a contiguous 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: The array is split about log n times, and at each level, the crossing sum loops run over parts of the array.

How Execution Grows With Input

At each step, the problem splits into two halves, and the crossing sum checks elements around the middle.

Input Size (n)	Approx. Operations
10	About 30 to 40 operations
100	About 700 to 800 operations
1000	About 10,000 to 12,000 operations

Pattern observation: The operations grow a bit faster than linear but slower than quadratic, roughly n log n growth.

Final Time Complexity

Time Complexity: O(n log n)

This means the time needed grows a little more than directly proportional to the input size, multiplied by the number of times we split the array.

Common Mistake

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

[OK] Correct: Although the array splits in half, at each level we still do work scanning parts of the array, so the total work adds up to more than just O(log n).

Interview Connect

Understanding this divide and conquer approach helps you see how breaking problems down can save time compared to checking every possibility, a skill useful in many coding challenges.

Self-Check

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