More Divide and Conquer · Algorithms (DAA)

Finding the maximum and minimum

Finding both the max and min of n numbers naively takes 2(n − 1) comparisons. Divide and conquer does it in about 3n/2 − 2:

Split the array in half; find (max, min) of each half recursively.
Combine with two comparisons: max of the maxes, min of the mins.

T(n) = 2T(n/2) + 2, T(2) = 1, T(1) = 0 → T(n) = 3n/2 − 2 for n a power of two.

C++

#include <iostream>
#include <vector>
using namespace std;

int comps = 0;

pair<int, int> maxMin(const vector<int> &a, int lo, int hi) {
    if (lo == hi) return {a[lo], a[lo]};
    if (hi == lo + 1) {
        comps++;
        return a[lo] > a[hi] ? make_pair(a[lo], a[hi]) : make_pair(a[hi], a[lo]);
    }
    int mid = (lo + hi) / 2;
    auto [max1, min1] = maxMin(a, lo, mid);
    auto [max2, min2] = maxMin(a, mid + 1, hi);
    comps += 2;
    return {max(max1, max2), min(min1, min2)};
}

int main() {
    vector<int> a = {22, 13, -5, -8, 15, 60, 17, 31, 47, 9, 3, 50, 2, 41, 11, 28};
    auto [mx, mn] = maxMin(a, 0, (int)a.size() - 1);
    cout << "max " << mx << ", min " << mn << ", comparisons " << comps
         << " (naive: " << 2 * (a.size() - 1) << ")" << endl;
    return 0;
}

Output

max 60, min -8, comparisons 22 (naive: 30)

Try it Yourself

Counting inversions

An inversion is a pair i < j with a[i] > a[j]. The count measures how "unsorted" an array is (used in ranking similarity, e.g. comparing two people's movie rankings). Checking all pairs is Θ(n²). Piggyback on merge sort: while merging, whenever an element from the right half is placed before remaining left-half elements, it forms an inversion with each of them.

C++

#include <iostream>
#include <vector>
using namespace std;

long long mergeCount(vector<int> &a, int lo, int hi) {
    if (lo >= hi) return 0;
    int mid = (lo + hi) / 2;
    long long inv = mergeCount(a, lo, mid) + mergeCount(a, mid + 1, hi);
    vector<int> tmp;
    int i = lo, j = mid + 1;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp.push_back(a[i++]);
        else { tmp.push_back(a[j++]); inv += mid - i + 1; }   // a[j] beats all remaining left elements
    }
    while (i <= mid) tmp.push_back(a[i++]);
    while (j <= hi) tmp.push_back(a[j++]);
    copy(tmp.begin(), tmp.end(), a.begin() + lo);
    return inv;
}

int main() {
    vector<int> a = {2, 4, 1, 3, 5};
    vector<int> b = {5, 4, 3, 2, 1};
    cout << "inversions in {2,4,1,3,5}: " << mergeCount(a, 0, 4) << endl;   // (2,1) (4,1) (4,3)
    cout << "inversions in {5,4,3,2,1}: " << mergeCount(b, 0, 4) << endl;   // n(n-1)/2
    return 0;
}

Output

inversions in {2,4,1,3,5}: 3
inversions in {5,4,3,2,1}: 10

Try it Yourself

Θ(n log n) instead of Θ(n²).

Karatsuba multiplication

Multiplying two n-digit numbers the school way takes Θ(n²) digit operations. Split each number into halves: x = a·10^m + b and y = c·10^m + d. Then

x·y = ac·10^(2m) + (ad + bc)·10^m + bd.

That needs four half-size products: T(n) = 4T(n/2) + O(n) = Θ(n²) — no gain. Karatsuba's trick (1960) computes the middle term with one extra product:

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

So only three multiplications are needed: T(n) = 3T(n/2) + O(n) = Θ(n^1.585).

C++

#include <iostream>
#include <cmath>
using namespace std;

long long karatsuba(long long x, long long y) {
    if (x < 10 || y < 10) return x * y;
    int digits = max(to_string(x).size(), to_string(y).size());
    int m = digits / 2;
    long long p = (long long)pow(10, m);
    long long a = x / p, b = x % p, c = y / p, d = y % p;
    long long ac = karatsuba(a, c);
    long long bd = karatsuba(b, d);
    long long mid = karatsuba(a + b, c + d) - ac - bd;     // = ad + bc with one multiplication
    return ac * p * p + mid * p + bd;
}

int main() {
    long long x = 12345678, y = 87654321;
    cout << karatsuba(x, y) << endl;
    cout << x * y << " (built-in, for comparison)" << endl;
    return 0;
}

Output

1082152022374638
1082152022374638 (built-in, for comparison)

Try it Yourself

Strassen's matrix multiplication

Ordinary multiplication of two n × n matrices takes Θ(n³). Splitting each matrix into four (n/2) × (n/2) blocks gives 8 block multiplications: T(n) = 8T(n/2) + Θ(n²) = Θ(n³).

Strassen (1969) found a way to combine the blocks using only 7 multiplications (and 18 additions/subtractions):

Product	Formula
M₁	(A₁₁ + A₂₂)(B₁₁ + B₂₂)
M₂	(A₂₁ + A₂₂)B₁₁
M₃	A₁₁(B₁₂ − B₂₂)
M₄	A₂₂(B₂₁ − B₁₁)
M₅	(A₁₁ + A₁₂)B₂₂
M₆	(A₂₁ − A₁₁)(B₁₁ + B₁₂)
M₇	(A₁₂ − A₂₂)(B₂₁ + B₂₂)

C₁₁ = M₁ + M₄ − M₅ + M₇, C₁₂ = M₃ + M₅, C₂₁ = M₂ + M₄, C₂₂ = M₁ − M₂ + M₃ + M₆.

T(n) = 7T(n/2) + Θ(n²) = Θ(n^log₂7) ≈ Θ(n^2.81).

C++

#include <iostream>
using namespace std;

int main() {      // Strassen's seven products on 2x2 matrices of numbers
    int a11 = 1, a12 = 3, a21 = 7, a22 = 5;
    int b11 = 6, b12 = 8, b21 = 4, b22 = 2;
    int m1 = (a11 + a22) * (b11 + b22), m2 = (a21 + a22) * b11, m3 = a11 * (b12 - b22);
    int m4 = a22 * (b21 - b11), m5 = (a11 + a12) * b22, m6 = (a21 - a11) * (b11 + b12);
    int m7 = (a12 - a22) * (b21 + b22);
    cout << "Strassen: " << m1 + m4 - m5 + m7 << " " << m3 + m5 << " / " << m2 + m4 << " " << m1 - m2 + m3 + m6 << endl;
    cout << "Normal:   " << a11 * b11 + a12 * b21 << " " << a11 * b12 + a12 * b22 << " / "
         << a21 * b11 + a22 * b21 << " " << a21 * b12 + a22 * b22 << endl;
    return 0;
}

Output

Strassen: 18 14 / 62 66
Normal:   18 14 / 62 66

Try it Yourself

Test yourself

4 questions · pick an answer to check it instantly

1
How many comparisons does divide-and-conquer max–min use for n = 16?
2
How many inversions does [3, 1, 2] have?
3
What is the running time of Karatsuba multiplication?
4
How many recursive multiplications does Strassen's algorithm use per level?

#Finding the maximum and minimum

#Counting inversions

#Karatsuba multiplication

#Strassen's matrix multiplication

Test yourself

Finding the maximum and minimum

Counting inversions

Karatsuba multiplication

Strassen's matrix multiplication