일반적으로 감소 정복 패러다임에서 더 작은 문제의 크기가 반드시 n - 1일 필요는 없다. 보통 하나씩 줄이는 방법이 가장 흔하지만 문제의 크기가 더 크게 줄어들기도 한다. 만약 매번 반복할 때마다 1/2 같은 식으로 상수 배율만큼씩 문제의 크기를 줄일 수 있다면 매우 빠른 알고리즘을 얻을 수 있다. 다음과 같은 게임이 그 대표적인 예라고 할 수 있다.

숫자 맞히기(스무고개) 1 이상, n 이하의 어떤 정해진 구간 안에 있는 어떤 정수에 대해 “예/아니오”로 답할 수 있는 질문으로 그 정수를 알아내라.

이 문제의 답을 가장 빠르게 알아내는 알고리즘은 매번 답이 들어 있는 구간을 절반씩으로 줄일 수 있게 질문하는 것이다. 예를 들어 첫 번째 질문에서 정답이 ⌈n/2⌉(n/2을 가장 가까운 정수로 올림한 값)보다 큰지 물어본다.²

이 알고리즘은 단계마다 인스턴스의 크기(정답이 들어 있을 수 있는 수의 구간)를 절반씩으로 줄일 수 있기 때문에 엄청나게 빠르게 돌아간다. 예를 들어 n = 1000000이더라도 동전 여덟 개 중에서 가짜 동전 찾아내기(2.010) 퍼즐도 감소 정복 전략의 한 예로, 상수 배율씩 줄이는 방법을 보여주는 대표적인 문제다.

큰 인스턴스와 작은 인스턴스의 관계를 작은 인스턴스에서 시작해 적용하는 것이 더 쉬울 수도 있다. 먼저 가장 작은 인스턴스에 대해 퍼즐을 푼 후 큰 문제, 다시 그 다음으로 큰 문제 순으로 문제를 키워가는 식이다. 이런 방법을 점증적 접근법(incremental approach)이라고 부른다. 직사각형 분할 퍼즐(2.003)이 대표적인 예라고 할 수 있다. 스무 번 안에 정답을 맞힐 수 있다. 단계별로 인스턴스 크기를 최대 1/3까지 줄여 정답을 더 빠르게 맞힐 수도 있다.