Decrease by Factor & Variable-Size Decrease

Decrease-and-Conquer by a Factor and Variable-Size Decrease

Unlike decrease-by-a-constant, decrease-by-a-constant-factor reduces the problem instance size by a multiplicative factor (usually $b = 2$, though sometimes $b = 3$). Variable-size-decrease algorithms reduce instance size by an amount that varies dynamically from step to step.

1. Decrease-by-a-Constant-Factor

Binary Search (Factor of 2)

Given a sorted array $A[0..n-1]$ and target key $K$, compare $K$ with the middle element $A[m]$. If unequal, discard half the array and continue searching in the remaining sub-array of size $\lfloor n/2 \rfloor$.

BinarySearch(A[0..n-1], K):
    l = 0
    r = n - 1
    while l <= r do:
        m = floor((l + r) / 2)
        if K == A[m] return m
        else if K < A[m] r = m - 1
        else l = m + 1
    return -1

Watch the search window collapse. Each comparison discards half of what is left, which is why only a handful of steps are needed for a 13-element array:

1BinarySearch(A[0..n-1], K):2    l = 03    r = n - 14    while l <= r do:5        m = floor((l + r) / 2)6        if K == A[m] return m7        else if K < A[m] r = m - 18        else l = m + 19    return -1

• Recurrence for Worst-Case Comparisons:

• Solution:

Fake-Coin Problem (Factor of 3)

Given $n$ identical-looking coins with 1 lighter fake coin and a balance scale:

1. Divide $n$ coins into three piles: two equal piles of size $\lfloor n/3 \rfloor$ and one pile with the remaining coins.
2. Weigh the two equal piles:
   • If they balance: The fake coin is in the third pile.
   • If they don’t balance: The fake coin is in the lighter pile.
3. Recurse on the pile containing the fake coin.

• Recurrence:

Ternary decrease requires strictly fewer weighings than binary halving because $\log_3 n < \log_2 n$.

Russian Peasant Multiplication

Multiplies two positive integers $n$ and $m$ using only halving, doubling, and addition:

Example: $50 \times 65$

• Number of steps: $\lfloor \log_2 n \rfloor + 1 = \Theta(\log n)$.

2. Variable-Size-Decrease Algorithms

Interpolation Search

For an array sorted with uniformly distributed numerical keys, instead of probing the midpoint, estimate the key’s position using linear interpolation:

• Average-Case Complexity: $\Theta(\log \log n)$ comparisons.
• Worst-Case Complexity: $\Theta(n)$ (if keys grow exponentially or are clustered).

Euclid’s Algorithm for Greatest Common Divisor (GCD)

Computes $\gcd(m, n)$ for non-negative integers where $m \ge n$:

The decrease in argument size varies per step, but $m \bmod n < m / 2$ guaranteed every two steps.

• Lamé’s Theorem: The number of division steps is at most $5 \times (\text{number of digits of } n)$.
• Time Complexity: $\Theta(\log n)$.

Summary of Decrease-and-Conquer Variants

Exercises