Divide and Conquer Strategy and Recurrence Relations in DSA Typescript - Time & Space Complexity

Time Complexity: Divide and Conquer Strategy and Recurrence Relations

O(n)

Understanding Time Complexity

Divide and conquer breaks a big problem into smaller parts, solves each part, then combines results.

We want to know how the time to solve grows as the problem size grows.

Scenario Under Consideration

Analyze the time complexity of this divide and conquer example.

function divideAndConquer(arr: number[], start: number, end: number): number {
  if (start > end) return 0;
  if (start === end) return arr[start];
  const mid = Math.floor((start + end) / 2);
  const left = divideAndConquer(arr, start, mid);
  const right = divideAndConquer(arr, mid + 1, end);
  return left + right;
}
    

This function splits the array into halves, sums each half recursively, then adds the results.

Identify Repeating Operations

Look for repeated work in the code.

• Primary operation: Recursive calls splitting the array into halves.
• How many times: Each call splits the problem into two smaller parts until size 1.

How Execution Grows With Input

Each step splits the problem in two, doing work on smaller parts.

Input Size (n)	Approx. Operations
10	About 19 calls (splits and sums)
100	About 199 calls
1000	About 1999 calls

Pattern observation: The number of calls grows linearly with n.

Final Time Complexity

Time Complexity: O(n)

This means the total work grows linearly with the size of the input array.

Common Mistake

[X] Wrong: "Because it splits the problem in half each time, the time is O(log n)."

[OK] Correct: Each level of splitting does work on all elements, so total work adds up to O(n), not just O(log n).

Interview Connect

Understanding how divide and conquer breaks problems down and how to analyze their time helps you solve many common coding challenges confidently.

Self-Check

What if the function combined results with a loop over the entire array segment instead of just adding two values? How would the time complexity change?