15.2 Divide and Conquer Strategies

Divide and conquer strategies break complex problems into smaller, manageable subproblems. This approach recursively solves each subproblem, then combines the solutions to tackle the original issue. It's a powerful method for designing efficient algorithms.

Merge sort and quick sort are prime examples of divide and conquer in action. These sorting algorithms demonstrate how breaking down a problem can lead to efficient solutions, often achieving time complexities of O(n log n) for sorting operations.

Divide and Conquer Strategies

Divide and conquer paradigm

• Algorithmic approach breaks down complex problems into smaller, more manageable subproblems
• Solves each subproblem recursively until they become simple enough to solve directly (base case)
• Combines the solutions of the subproblems to construct the solution to the original problem
• Recursive nature applies the same divide and conquer strategy to subproblems until reaching the base case
• Solutions to subproblems are combined as the recursion unwinds to solve the original problem (binary search, merge sort)

Design of divide and conquer algorithms

• Merge sort algorithm:
  1. Divides unsorted list into $n$ single-element sublists (considered sorted)
  2. Merges sublists repeatedly to create larger sorted sublists
  3. Continues merging until only one sorted sublist remains (the fully sorted list)
  • Time complexity of $O(n \log n)$ for all cases (best, average, worst)
• Quick sort algorithm:
  1. Selects a pivot element from the list (first, last, or random element)
  2. Partitions the list around the pivot, creating two sublists:
     • Elements less than or equal to the pivot
     • Elements greater than the pivot
  3. Recursively applies quick sort to the sublists
  • Average-case time complexity of $O(n \log n)$
  • Worst-case time complexity of $O(n^2)$ (already sorted or reverse-sorted list)

Time complexity of divide and conquer

• Recurrence relations express running time in terms of subproblem running times
• Merge sort recurrence: $T(n) = 2T(n/2) + O(n)$
  • $2T(n/2)$ represents time for recursive subproblem solving
  • $O(n)$ represents time for merging subproblem solutions
• Quick sort average-case recurrence: $T(n) = 2T(n/2) + O(n)$
  • $2T(n/2)$ represents time for recursive subproblem solving
  • $O(n)$ represents time for list partitioning
• Master Theorem or recursion tree method solves recurrences to determine overall time complexity

Divide and conquer vs other techniques

• Greedy algorithms make locally optimal choices hoping for a global optimum
  • May not guarantee optimal solution (Dijkstra's algorithm, Huffman coding)
• Dynamic programming breaks problems into overlapping subproblems
  • Stores results for reuse (memoization) to avoid redundant calculations
  • Improves efficiency (Fibonacci sequence, longest common subsequence)
• Divide and conquer breaks problems into non-overlapping subproblems
  • Combines subproblem solutions to solve original problem
  • Guarantees optimal solution for certain problems (merge sort, quick sort)
  • Higher space complexity due to recursive calls