Subtract-and-Conquer Recurrence Growth

Intuition

A recurrence like $T(n)=aT(n-b)+f(n)$ is subtract-and-conquer: the argument decreases by a fixed amount $b$, not by a dividing factor. The Master Theorem (built for $T(n)=aT(n/b)+f(n)$) does not apply. Instead, unroll level by level. The recursion has depth $\approx n/b$, and each level multiplies the count of subproblems by $a$, so the leaf count is $a^{n/b}$.

Result / Method

For $T(n)=aT(n-1)+d$ (constant $d$):

• If $a=1$: $T(n)=\Theta(n)$ (just adding $d$ at each of $n$ levels).
• If $a>1$: $T(n)=\Theta(a^n)$, exponential. The geometric sum is dominated by its largest term.

General pattern: $T(n)=aT(n-b)+\Theta(n^k)$ gives $\Theta(n^k)$ if $a<1$... but for the konkur case $a\ge 2$ the answer is exponential, $\Theta(a^{n/b})$.

Worked example (Q68)

Given $T(1)=c$, $T(n)=2T(n-1)+d$. Unroll:

T(n) = 2T(n-1) + d
     = 4T(n-2) + 2d + d
     = 8T(n-3) + 4d + 2d + d
     = ...
     = 2^(n-1) T(1) + d * (2^(n-1) - 1)
     = (c+d) * 2^(n-1) - d

The geometric sum $\sum_{i=0}^{n-2}2^i = 2^{n-1}-1$. Since $c,d$ are constants, $T(n)=\Theta(2^n)=O(2^n)$.

Pitfall: Do not confuse $T(n)=2T(n-1)+d$ (argument decreases by 1 -> $\Theta(2^n)$, exponential) with $T(n)=2T(n/2)+d$ (argument halved -> $\Theta(n)$ by the Master Theorem). The minus sign versus division completely changes the growth rate.