Divide and conquer applications

Why it exists

The last page defined the method; this page applies it to the problems that appear in courses and exams, and for each one answers the same three questions: how is the problem cut, how are the answers combined, and what recurrence results. Several of these algorithms are famous because they beat an obvious method by changing the exponent (multiplying two $n$-digit numbers in $n^{1.585}$ instead of $n^2$ steps, two $n \times n$ matrices in $n^{2.807}$ instead of $n^3$), and GATE tests exactly those exponents.

Prerequisites

You need the paradigm and the Master theorem (divide and conquer).

Precise definitions

All problems below are solved with recurrences of the form $T(n) = a\,T(n/b) + f(n)$ (divide and conquer), apart from selection. The new definitions:

Maximum subarray. Given numbers $a_0, \ldots, a_{n-1}$ (some negative), find $\max_{i \le j} (a_i + \cdots + a_j)$ over non-empty contiguous ranges.

Inversion. A pair $i < j$ with $a_i > a_j$ (see elementary sorts).

Closest pair. Given $n$ points in the plane, find two distinct points at the smallest Euclidean distance.

Selection (order statistic). Find the $k$-th smallest of $n$ keys; the median is $k = \lceil n/2 \rceil$.

How it works

The table collects the recurrences of the algorithms of this and the previous pages. Each Master-form row was decided by the decision procedure of the recurrence page and confirmed by evaluating the recurrence.

Fast exponentiation

To compute $x^n$: if $n = 1$ the answer is $x$; otherwise compute $h = x^{\lfloor n/2 \rfloor}$, square it, and multiply by $x$ once more if $n$ is odd. Since $x^n = (x^{n/2})^2$ for even $n$ and $x \cdot (x^{(n-1)/2})^2$ for odd $n$, this is correct. One subproblem of half the size and a constant amount of work: $T(n) = T(n/2) + \Theta(1)$, so $\Theta(\log n)$ multiplications instead of the $n - 1$ of a loop. Exactly $\lfloor \log_2 n \rfloor$ squarings and $(\text{number of 1 bits of } n) - 1$ extra multiplications are made, at most $2 \lfloor \log_2 n \rfloor$ in total. The program counts them (modulo a prime-sized number to keep the values small) and checks the result against the loop.

#include <stdio.h>
 
#define MOD 1000003ULL
 
static long mults;
 
/* x^n mod MOD by repeated squaring, n >= 1: T(n) = T(n/2) + (1 or 2) multiplications */
static unsigned long long power(unsigned long long x, unsigned n) {
    if (n == 1) return x % MOD;
    unsigned long long h = power(x, n / 2);
    unsigned long long r = h * h % MOD;     /* the squaring */
    mults++;
    if (n % 2 == 1) {                       /* an odd exponent needs one more multiplication */
        r = r * x % MOD;
        mults++;
    }
    return r;
}
 
int main(void) {
    unsigned ns[] = {2, 7, 8, 100, 1000, 1023, 1024, 1000000};
    printf("%8s %6s %8s %s\n", "n", "mults", "n - 1", "same result as the loop");
    for (int t = 0; t < 8; t++) {
        unsigned n = ns[t];
        mults = 0;
        unsigned long long fast = power(3, n);
        unsigned long long slow = 3;
        for (unsigned i = 1; i < n; i++) slow = slow * 3 % MOD;
        printf("%8u %6ld %8u %s\n", n, mults, n - 1, fast == slow ? "yes" : "NO");
    }
    return 0;
}

       n  mults    n - 1 same result as the loop
       2      1        1 yes
       7      4        6 yes
       8      3        7 yes
     100      8       99 yes
    1000     14      999 yes
    1023     18     1022 yes
    1024     10     1023 yes
 1000000     25   999999 yes

For $n = 1000 = 1111101000_2$: $9$ squarings and $5$ extra multiplications (six 1 bits minus one) give the $14$ of the table. The worst case for a given length is $n = 2^k - 1$ (all bits one): $n = 1023$ needs $18 = 2 \cdot 9$.

Maximum subarray

Cut the array in the middle. The best range is entirely in the left half, entirely in the right half, or crosses the middle. The first two are the recursive calls. The best crossing range is the best suffix of the left half plus the best prefix of the right half, found by two scans of total length $n$. So $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)$. (A single left-to-right scan that keeps the best sum ending at the current position, Kadane's algorithm, solves it in $\Theta(n)$ and is a dynamic programming idea.)

Counting inversions

Run merge sort and count while merging (merge sort). When the merge takes a key from the right half, it is smaller than all keys still waiting in the left half, so it forms one inversion with each of them: add the number of keys left in the left half. Inversions inside a half are counted by the recursive calls, so the total is left + right + crossing. The merge is linear: $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)$, against $\Theta(n^2)$ for checking all pairs. For $5, 1, 4, 2, 8, 7, 3$ split as $5, 1, 4$ and $2, 8, 7, 3$: the left half has $2$ inversions, the right $3$, and $4$ pairs cross ($5$ and $4$ each exceed $2$ and $3$), in total $9$, the number found earlier by counting directly.

Karatsuba multiplication

Write two $n$-digit numbers as $x = x_1 B + x_0$ and $y = y_1 B + y_0$, with $B = 2^{n/2}$ (or $10^{n/2}$). Then $xy = x_1 y_1 B^2 + (x_1 y_0 + x_0 y_1) B + x_0 y_0 .$ The schoolbook method makes four half-size products, $T(n) = 4T(n/2) + \Theta(n) = \Theta(n^2)$. Karatsuba's idea: with $z_2 = x_1 y_1$, $z_0 = x_0 y_0$ the middle term is $x_1 y_0 + x_0 y_1 = (x_1 + x_0)(y_1 + y_0) - z_2 - z_0,$ a third half-size product, so only three products are needed, plus additions and shifts that cost $\Theta(n)$: $T(n) = 3T(n/2) + \Theta(n) = \Theta(n^{\log_2 3}) = \Theta(n^{1.585}).$

Strassen's matrix multiplication

Split each $n \times n$ matrix into four $n/2 \times n/2$ blocks. The block formulas for $C = AB$ need eight block products, $T(n) = 8T(n/2) + \Theta(n^2) = \Theta(n^3)$. Strassen found seven:

$C_{11} = M_1 + M_4 - M_5 + M_7,\quad C_{12} = M_3 + M_5,\quad C_{21} = M_2 + M_4,\quad C_{22} = M_1 - M_2 + M_3 + M_6 .$ It uses $18$ additions or subtractions of half-size matrices (each $\Theta(n^2)$), so $T(n) = 7T(n/2) + \Theta(n^2) = \Theta(n^{\log_2 7}) = \Theta(n^{2.807}).$ The identities were checked symbolically, and a C program (not printed here; it is in scripts/gen-algo-sort-traces.py) multiplied random integer matrices both ways: the products agree, the number of scalar multiplications is $8^k$ for the classical method and $7^k$ for Strassen's, $n = 2^k$.

Because the saving is a constant factor $(7/8)^k$ with a larger constant in the additions, Strassen's method pays off only for large matrices. The formulas never swap the two factors of a product, so they are valid for blocks, which do not commute.

Closest pair of points

Sort the points by $x$ once (and by $y$ once). Cut by a vertical line into two halves of $n/2$ points; solve each; let $\delta$ be the smaller of the two closest distances. A closer pair must have one point on each side, and both points are within $\delta$ of the line, so only the strip of points within $\delta$ of the line matters. Sort the strip points by $y$ and compare each with the next few points in $y$ order: a point has at most $7$ later points with a $y$-difference below $\delta$. Such points lie in a rectangle of width $2\delta$ and height $\delta$ above it, made of two $\delta \times \delta$ squares (one on each side of the line); the points on one side are at least $\delta$ apart, so each square holds at most $4$ of them, at most $8$ points including the point itself. So the combine step is linear, if the points are kept in $y$ order by merging (as merge sort does): $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n).$ If instead the strip is sorted from scratch at every level, the combine step is $\Theta(n \log n)$ and the total becomes $\Theta(n \log^2 n)$. A concrete case: the points $(1,1), (4,5), (6,2), (7,8)$ on the left and $(8,3), (11,9), (13,4), (15,7)$ on the right. Both halves have closest distance $\sqrt{13} \approx 3.61$ (pairs $(4,5)$–$(6,2)$ and $(13,4)$–$(15,7)$). The strip around $x = 7.5$ holds the points with $x$ from $4$ to $11$; sorted by $y$ they are $(6,2), (8,3), (4,5), (7,8), (11,9)$; the very first neighbours already give $(6,2)$–$(8,3)$ at distance $\sqrt 5 \approx 2.24$, the overall answer (checked against all $28$ pairs).

Selection in linear time

Quickselect partitions around a pivot and recurses on the side that contains the $k$-th key: expected $\Theta(n)$ time, worst case $\Theta(n^2)$ (quicksort). The median of medians makes the pivot good: split the keys into groups of $5$, find each group's median (constant time per group), find the median $p$ of these $\lceil n/5 \rceil$ medians recursively, and use $p$ as the pivot. At least about $3n/10 - 6$ keys are smaller than $p$ and as many are larger (half of the group medians are at least $p$, and each of those groups has three keys at least $p$), so the recursive call on one side has at most $7n/10 + 6$ keys: $T(n) \le T(\lceil n/5 \rceil) + T(7n/10 + 6) + \Theta(n).$ Since $1/5 + 7/10 = 9/10 < 1$ the solution is $\Theta(n)$ (each level's total size shrinks by a constant factor, so the work is a geometric series dominated by the top). With groups of $3$ the fractions would be $1/3 + 2/3 = 1$, the recurrence $T(n/3) + T(2n/3) + \Theta(n)$ solves to $\Theta(n \log n)$, and no linear bound follows; groups of $7$ also work. The constants are large, so quickselect is used in practice.

Worked examples

Cheat box

Traps and GATE patterns

Connections

These algorithms are instances of divide and conquer whose recurrences are solved in solving recurrences. Counting inversions is merge sort with a counter (merge sort); the partition used by quickselect is that of quicksort. Kadane's linear scan for the maximum subarray is a dynamic programming idea, like the problems in dynamic programming on sequences.

PYQs

Let P be an array containing n integers. Let t be the
lowest upper bound on the number of comparisons
of the array elements, required to find the minimum
and maximum values in an arbitrary array of n
elements. Which one of the following choices is
correct?

Consider a sequence of 14
elements:A=[-5,-10,6,3,-1,-2,13,4,-9,-1,4,12,-3
,0].The sequence sum S(i, j) = ∑j k=i
A[k].Determine the maximum of S(i ,j), where 0≤
i≤ j< 14.(Divide and conquer approach may be
used.)

The minimum number of comparisons required
finding the minimum and the maximum of 100
numbers is
ALGORITHMS

Check Out Our Gate Courses & Secure Your Dream Rank !

HINTS & SOLUTIONS

Self-check

Revision card

References