Unit 2: Divide and Conquer

I. Orientation — The Divide-and-Conquer Paradigm

Divide and conquer is an algorithm-design method that solves a problem by splitting it into smaller instances of the same problem, solving those instances, and combining their solutions. Its efficiency depends on the number and size of subproblems, the recursion depth, and the work performed outside recursive calls.

A. General method

The general method consists of divide, conquer, and combine stages applied recursively until directly solvable base cases are reached.

• Divide: Partition an input of size (n) into (a) smaller subproblems, commonly of size (n/b).
  • (n): size of the original input.
  • (a): number of recursive subproblems.
  • (b): factor by which each subproblem’s size is reduced.
• Conquer: Solve each subproblem recursively; when a subproblem reaches a base size such as (n=0) or (n=1), return its solution directly.
• Combine: Construct the original problem’s solution from the subproblem solutions. Merge sort, for example, combines two sorted lists by merging them.
• Correctness principle: Recursive correctness is commonly established by induction:
  1. Prove that the base case is solved correctly.
  2. Assume recursive calls correctly solve smaller inputs.
  3. Prove that dividing and combining produce the correct solution for size (n).
• Typical recurrence: Running time is represented by:

T(n) = aT(n/b) + f(n)

• (T(n)): total time for an input of size (n).
• (aT(n/b)): time spent solving (a) subproblems.
• (f(n)): time used for division and combination.
  • Master-theorem comparison: For (T(n)=aT(n/b)+f(n)), compare (f(n)) with (n^{\log_b a}).
• If (f(n)) grows polynomially more slowly, recursive work dominates.
• If both have the same asymptotic order, the levels contribute comparably.
• If (f(n)) grows polynomially faster and satisfies the regularity condition, divide-and-combine work dominates.
  • Recursion-tree interpretation: Each node represents one subproblem, each level represents one stage of recursive reduction, and the level costs are summed to obtain (T(n)).
  • Advantages: Balanced subproblems often yield logarithmic recursion depth, expose parallelism, and improve cache behavior by operating on progressively smaller data.
  • Limitations: Poorly balanced partitions can create deep recursion; combining may be expensive; recursive calls require stack space; and overlapping subproblems may be better handled by dynamic programming.

II. Binary Search — Halving an Ordered Search Space

Binary search locates a target in a sorted sequence by comparing it with the middle element and discarding the half that cannot contain it.

A. Binary search

Binary search maintains a candidate interval and reduces its length by approximately one-half after every unsuccessful comparison.

• Precondition: The sequence must be sorted according to the same ordering used in comparisons; for ascending data, (A[i]\leq A[i+1]).
• Invariant: At the start of each iteration, if target (x) occurs in the array, it lies between indices low and high, inclusive.
• Decision rule:
  1. If (A[mid]=x), return mid.
  2. If (A[mid]<x), continue in the right half.
  3. If (A[mid]>x), continue in the left half.
• Iterative algorithm:

BINARY-SEARCH(A, x):
    low = 0
    high = length(A) - 1
    while low <= high:
        mid = low + floor((high - low) / 2)
        if A[mid] == x:
            return mid
        else if A[mid] < x:
            low = mid + 1
        else:
            high = mid - 1
    return NOT_FOUND

• (A): sorted array; (x): target value.
• low, high: current interval boundaries.
• mid: middle index; the stated calculation avoids overflow from low + high.
  • Worked example: In (A=[3,7,11,18,24,31,42]), searching for (24) first checks (18) at index (3), discards indices (0)–(3), and then checks (24) at index (4).
  • Time complexity: The recurrence is (T(n)=T(n/2)+\Theta(1)), giving (\Theta(\log n)) in the worst and average cases; a first-comparison match takes (\Theta(1)).
  • Space complexity: The iterative form uses (\Theta(1)) auxiliary space, while a recursive implementation uses (\Theta(\log n)) stack space.
  • Limitation: Binary search is efficient for random-access structures such as arrays, but finding the middle of a linked list can require linear traversal.

III. Merge Sort — Balanced Sorting by Merging

Merge sort recursively sorts two halves of a sequence and combines them through a linear-time merge operation.

A. Merge sort

Merge sort guarantees balanced recursive division regardless of the original ordering of the input.

• Algorithm:

MERGE-SORT(A, left, right):
    if left >= right:
        return
    mid = floor((left + right) / 2)
    MERGE-SORT(A, left, mid)
    MERGE-SORT(A, mid + 1, right)
    MERGE(A, left, mid, right)

• (A): array being sorted.
• left, right: boundaries of the current segment.
• mid: endpoint of its left half.
  • Merge operation: Compare the first unconsumed elements of two sorted temporary sequences, copy the smaller one to the output, and finally copy any remainder.
  • Correctness: Recursive calls produce two sorted halves by the inductive hypothesis; selecting the smallest available front element ensures that each next output element is globally smallest among all unconsumed elements.
  • Complexity derivation:

T(n) = 2T(n/2) + Θ(n) = Θ(n log n)

• (2T(n/2)): sorting two halves.
• (\Theta(n)): merging all (n) elements.
• There are (\log_2 n) levels, each performing (\Theta(n)) merge work.
  • Case behavior: Best-, average-, and worst-case running times are all (\Theta(n\log n)), because splitting and merging do not depend on input order.
  • Stability: The sort is stable if, when values are equal, the merge takes the element from the left half first; equal keys then preserve their original order.
  • Space: Standard array merge sort needs (\Theta(n)) auxiliary storage plus (\Theta(\log n)) recursion-stack space.
  • Applications and limitations: Predictable performance and stability suit records and external sorting. Its main disadvantage for arrays is extra storage, although linked-list merging can rearrange pointers with little additional data space.

IV. Quick Sort — Partitioning Around a Pivot

Quick sort selects a pivot, partitions elements by their relation to it, and recursively sorts the resulting regions.

A. Quick sort

Quick sort gains practical speed from in-place partitioning, but its efficiency depends on pivot quality.

• Partition property: After partitioning around pivot (p), elements on one side satisfy (A[i]\leq p), elements on the other satisfy (A[j]>p), and the pivot occupies its final sorted position.
• Lomuto-style algorithm:

QUICK-SORT(A, low, high):
    if low < high:
        q = PARTITION(A, low, high)
        QUICK-SORT(A, low, q - 1)
        QUICK-SORT(A, q + 1, high)

• (A): array; low, high: segment boundaries.
• (q): final pivot index returned by PARTITION.
  • Partition mechanism: Using (A[high]) as pivot, scan from low to high - 1, maintain a boundary for values at most the pivot, swap qualifying values forward, and finally place the pivot after that boundary.
  • Worked example: Partitioning ([9,3,7,2,8]) around pivot (8) places (3,7,2) before it and (9) after it, producing a valid arrangement such as ([3,7,2,8,9]); the regions are not yet internally sorted.
  • Balanced case:

T(n) = 2T(n/2) + Θ(n) = Θ(n log n)

The linear term is partitioning, while balanced halves produce logarithmic recursion depth.

• Unbalanced case:

T(n) = T(n - 1) + Θ(n) = Θ(n²)

Repeatedly choosing the smallest or largest element leaves one subproblem of size (n-1), as can occur when an endpoint pivot is used on already sorted input.

• Pivot strategies: Random pivot selection makes consistently poor partitions unlikely; median-of-three uses the median of the first, middle, and last elements as a practical approximation.
• Space and stability: Partitioning is typically in-place, but recursion uses expected (\Theta(\log n)) stack space and worst-case (\Theta(n)). Standard quick sort is not stable because swaps can reverse equal-key records.
• Practical significance: Its expected (\Theta(n\log n)) time, low auxiliary storage, and locality often make it fast for arrays, despite the quadratic worst case.

V. Arithmetic with Large Integers — Recursive Multiplication

Large-integer arithmetic represents numbers using multiple digits or machine words because values exceed the processor’s fixed-width integer range.

A. Arithmetic with large integers

Divide-and-conquer multiplication reduces the number of recursive products by splitting each operand into high and low parts.

• Representation: In base (B), an (n)-digit integer is stored as digits (d_i), where (0\leq d_i<B):

X = Σ(d_i B^i), for i = 0 to n - 1

• (X): represented integer.
• (d_i): digit at position (i).
• (B): base, such as (10) or a machine-word power of (2).
  • Basic operations: Addition and subtraction scan digits while propagating carries or borrows, taking (\Theta(n)) time. Grade-school multiplication forms all digit pairs and takes (\Theta(n^2)).
  • Operand split: For (m) low-order digits, write:

X = aB^m + b
Y = cB^m + d
XY = acB^(2m) + (ad + bc)B^m + bd

• (a,c): high parts; (b,d): low parts.
• Four half-size products give (T(n)=4T(n/2)+\Theta(n)=\Theta(n^2)), so splitting alone provides no asymptotic improvement.
  • Karatsuba reduction: Compute only (ac), (bd), and ((a+b)(c+d)), using:

ad + bc = (a + b)(c + d) - ac - bd

This replaces four recursive multiplications with three.

• Complexity:

T(n) = 3T(n/2) + Θ(n)
     = Θ(n^(log₂3))
     ≈ Θ(n^1.585)

The linear term covers additions, subtractions, splitting, and positional shifts.

• Worked example: Split (1234) and (5678) at (m=2): (a=12), (b=34), (c=56), (d=78). Then (ac=672), (bd=2652), and ((a+b)(c+d)=46\cdot134=6164). Thus (ad+bc=6164-672-2652=2840), giving (672\cdot10^4+2840\cdot10^2+2652=7{,}006{,}652).
• Practical limitation: Karatsuba’s extra additions and recursive overhead make grade-school multiplication faster for small operands, so implementations switch algorithms at a chosen size threshold.