In the variable-size-decrease strategy, each step reduces the problem size by a non-fixed amount—often determined by a selection, partitioning, or transformation process that depends on the input itself. Unlike constant or constant-factor reductions, the size of the next subproblem is not predictable in advance. This variability makes analysis more nuanced, but many powerful algorithms—such as QuickSelect and Quicksort—rely on this approach to achieve optimal or near-optimal performance in practice.
Typically, these algorithms spend \(O(n)\) time on a partitioning or scanning step, followed by a recursive call on a subproblem of size \(k\), where \(k\) may range from 0 to \(n - 1\). In the best case, the reduction is large, leading to fast convergence; in the worst case, the progress is slow—sometimes resulting in poor time complexity unless additional strategies (like randomization or median-of-medians) are applied.
The Greatest Common Divisor (GCD) problem asks for the largest integer that divides two positive integers \(a\) and \(b\) without leaving a remainder. If you are unfamiliar with GCD, make sure you read the GCD page. While a brute-force approach would check all numbers from \(\min(a,b)\) down to 1, there is a much faster method based on a variable-size-decrease strategy.
The Euclidean Algorithm for computing \(\gcd(a, b)\) works as follows:
To understand why this works, recall that any number that divides both \(a\) and \(b\) (where \(a\ge b\)) must also divide the remainder when \(a\) is divided by \(b\)—that is, \(a \bmod b\). This is because we can write \(a = bq + r\), where \(r = a \bmod b\), and any common divisor of \(a\) and \(b\) must also divide \(r\). So the set of common divisors of \((a, b)\) is the same as that of \((b, a \bmod b)\), and thus their greatest common divisor is the same.
Intuitively, the Euclidean Algorithm works by replacing the original problem with a "smaller but equivalent" one: instead of asking "what divides both \(a\) and \(b\)?", we ask "what divides both \(b\) and the leftover part of \(a\) after removing as many full \(b\)'s as possible?"
At each step, the size of the problem decreases from \((a,b)\) to \((b, a \bmod b)\), but the amount it decreases depends on the values of \(a\) and \(b\). In the worst case, it may only shrink slightly; in the best case, it decreases rapidly. This makes it a clear example of a variable-size-decrease algorithm.
Here's more formal pseudocode for the recursive version of the algorithm:
gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)The following demonstration shows the algorithm in action.
Time Complexity: Let \(T(a,b)\) be the time to compute \(\gcd(a,b)\). Each recursive call performs a constant-time modulus operation and then recurses on \(\bigl(b,\;a \bmod b\bigr)\). In the worst case—when \((a,b)\) are consecutive Fibonacci numbers—this recursion makes only \(O(\log b)\) steps, so \[ T(a,b) \;=\; O(\log b) \;=\; O\bigl(\log \min(a,b)\bigr). \] Thus the Euclidean Algorithm runs in time logarithmic in the smaller of its two inputs, making it extremely efficient even for very large integers. (We realize we skimped on the details of this analysis. If you are really interested in understanding the details, you can find them in various other places including Euclidean Algorithm (Wikipedia).)
Quickselect solves the kth order statistic problem, which is simply to determine the \(k\)-th smallest element in a (presumably unsorted) array. It works as follows:
Here is a very simple demo showing a high-level view of Quickselect. It glosses over the details of the partition step, but it should give you a general idea of how the algorithm works.
Notice that once the algorithm has finished, the element at the desired index (in this case \(k=5\)) is in the proper location, elements smaller are to the left, and elements larger are to the right, but the array is not totally ordered. Quickselect orders it just enough to be able to put the \(k\)-th element in place.
Time Complexity: On average Quickselect runs in \(O(n)\) time (with careful pivot selection), though in the worst case it can be \(O(n^2)\).
This algorithm is a lot like Quicksort, except it only recurses on one part instead of both. Because there are subtleties that make this algorithm a little more complicated than the other examples in this section, we defer full details, incuding pseudocode, to the Quickselect page.
Variable-Size-Decrease may be less suitable in these scenarios: