Substitution method

By means of the substitution method for recurrences, a lower limit or upper limit of the (computational) effort of a recursion can be determined.

Describe the method

A recursion T (n) of the form T (n) = a⋅T (n / b) + f (n) is given. In order to determine an upper bound, it is first estimated using the Ο-calculus . Estimating means “clever guessing”. The presumption is then proven or disproved with the help of substitution. The procedure for determining the lower limit is analogous.

1. Assumption ⁽¹⁾ : T (n) ≤ c⋅g (n), with c> 0 or T (n) ∈ Ο (g (n)) (according to the definition of the Ο-calculus)
2. Assumption ⁽²⁾ : T _sub (n / b) ≤ c⋅g (n / b)
3. Substitution by inserting the assumption into the recurrence: T (n) ≤ a⋅T _sub (n / b) + f (n) or T (n) ≤ a⋅ (c⋅g (n / b)) + f ( n)
4. Exact ⁽³⁾ conversion to: T (n) ≤ c⋅g (n) → If this is not possible, either the conjecture or the assumption ^{(2) was} wrong.
5. Proof of T (n) ≤ c⋅g (n) by induction ⇒ T (n) ∈ Ο (g (n))

(1)	The conjecture is the bound estimated upwards, so that: T (n) ≤ c⋅g (n) ∈Ο (g (n))
(2)	If at 4. T (n) cannot be transformed exactly (3) , one can subtract a term t (n) of lower order from the assumption T sub (n / b) ≤ c⋅g (n / b) . The new assumption is then: T sub (n / b) ≤ c⋅g (n / b) - t (n)
(3)	This means that z. B. T (n) ≤ (c + 1) ⋅g (n) is not the exact form of the conjecture. For example, T (n) ≤ c⋅g (n) or T (n) ≤ (c-1) ⋅g (n) would be correct.

example

• Example (1) :   ${\displaystyle T(n)=2T\left(\left\lfloor {\frac {n}{4}}\right\rfloor \right)+8T\left(\left\lfloor {\frac {n}{16}}\right\rfloor \right)+n}$

1st assumption: ${\displaystyle T(n)\in O(n\ln(n))\Longrightarrow T(n)\leq c\cdot n\ln(n)}$

2. Assumption:   and   ${\displaystyle T_{sub1}\left({\frac {n}{4}}\right)\leq c\cdot \left({\frac {n}{4}}\right)\ln \left({\frac {n}{4}}\right)}$ ${\displaystyle T_{sub2}\left({\frac {n}{16}}\right)\leq c\cdot \left({\frac {n}{16}}\right)\ln \left({\frac {n}{16}}\right)}$

3. Substitution: ${\displaystyle T(n)\leq 2\cdot T_{sub1}\left({\frac {n}{4}}\right)+8T_{sub2}\left({\frac {n}{16}}\right)+n}$

4. Forming:

${\displaystyle =2\left(c\cdot \left({\frac {n}{4}}\right)\ln \left({\frac {n}{4}}\right)\right)+8\left(c\cdot \left({\frac {n}{16}}\right)\ln \left({\frac {n}{16}}\right)\right)+n}$

${\displaystyle =c\cdot {\frac {n}{2}}\left(\ln(n)-\ln(4)\right)+c\cdot {\frac {n}{2}}\left(\ln(n)-\ln(16)\right)+n}$

${\displaystyle =c\cdot {\frac {n}{2}}\left(2\ln(n)-\ln(4)-\ln(16)\right)+n}$

${\displaystyle =c\cdot n\ln(n)-c\cdot {\frac {n}{2}}\left(\ln(4)+\ln(16)\right)+n}$

${\displaystyle \leq c\cdot n\ln(n)}$  With   ${\displaystyle c\geq {\frac {2}{\ln(4)+\ln(16)}}={\frac {2}{\ln(64)}}}$

5. Induction:

IA:    with   ${\displaystyle n=2:\quad T(2)=2\leq c\cdot 2\ln(2)=}$ ${\displaystyle c\geq \ln ^{-1}(2)\approx 1{,}443}$

IV:    for   ${\displaystyle T(n)\leq c\cdot n\ln(n)}$ ${\displaystyle n\geq n_{0}}$

IS: n → n + 1: Since it has been shown for an n ₀ that T (n) ≤ c⋅n⋅ln (n) is correct, the conjecture is correct. (It turns out that a constant c ≥ 1.443 is sufficient.)

Hence for T (n) it follows:   ${\displaystyle T(n)\in O(n\ln(n))}$

• Example (2) :   ${\displaystyle T(n)=8T\left({\frac {n}{2}}\right)+n^{3}\ln(n)}$

For the same example, see also the effort estimation with the Kalk-calculus in the article on the master theorem .

1st assumption: ${\displaystyle T(n)\in O\left(n^{3}\ln ^{2}(n)\right)\Longrightarrow T(n)\leq c\cdot n^{3}\ln ^{2}(n)}$

2. Assumption:   with     and   ${\displaystyle T_{sub}\left({\frac {n}{2}}\right)=c\cdot \left({\frac {n}{2}}\right)^{3}\ln ^{2}\left({\frac {n}{2}}\right)-t(n)}$ ${\displaystyle t(n)=b\cdot \ln ^{2}(2)\left({\frac {n}{2}}\right)^{3}}$ ${\displaystyle b>0}$

3. Substitution: ${\displaystyle T(n)\leq 8T_{sub}\left({\frac {n}{2}}\right)+n^{3}\ln(n)}$

4. Forming:

${\displaystyle =8\left(c\cdot \left({\frac {n}{2}}\right)^{3}\ln ^{2}\left({\frac {n}{2}}\right)-b\cdot \ln ^{2}(2)\left({\frac {n}{2}}\right)^{3}\right)+n^{3}\ln(n)}$

${\displaystyle =c\cdot n^{3}\ln ^{2}\left({\frac {n}{2}}\right)-b\cdot \ln ^{2}(2)n^{3}+n^{3}\ln(n)}$

${\displaystyle =c\cdot n^{3}\left(\ln(n)-\ln(2)\right)\cdot \left(\ln(n)-\ln(2)\right)-b\cdot \ln ^{2}(2)n^{3}+n^{3}\ln(n)}$

${\displaystyle =c\cdot n^{3}\left(\ln ^{2}(n)-2\ln(2)\ln(n)+\ln ^{2}(2)\right)-b\cdot \ln ^{2}(2)n^{3}+n^{3}\ln(n)}$

${\displaystyle =c\cdot n^{3}\ln ^{2}(n)-c\cdot n^{3}2\ln(2)\ln(n)+c\cdot n^{3}\ln ^{2}(2)-b\cdot \ln ^{2}(2)n^{3}+n^{3}\ln(n)}$

${\displaystyle =c\cdot n^{3}\ln ^{2}(n)-c\cdot n^{3}2\ln(2)\ln(n)+n^{3}\ln(n)-b\cdot \ln ^{2}(2)n^{3}+c\cdot n^{3}\ln ^{2}(2)}$

${\displaystyle =c\cdot n^{3}\ln ^{2}(n)+{\begin{matrix}\underbrace {n^{3}\ln(n)\cdot (1-c\cdot 2\ln(2))} \\{}^{\rm {c\geq {\frac {1}{2\ln(2)}}}}\\[-4.5ex]\end{matrix}}+{\begin{matrix}\underbrace {n^{3}\ln ^{2}(2)\cdot (c-b)} \\{}^{\rm {\ b\geq c}}\\[-4.5ex]\end{matrix}}}$

${\displaystyle \leq c\cdot n^{3}\ln ^{2}(n)}$  With   ${\displaystyle \ b\geq c\geq 2\ln ^{-1}(2)}$

5. Induction:

IA:    with   ${\displaystyle n=2:\quad T(2)\approx 5{,}5\leq c\cdot 2^{3}\ln ^{2}(2)}$ ${\displaystyle c\geq 1}$

IV:    for   ${\displaystyle T(n)\leq c\cdot n^{3}\ln ^{2}(n)}$ ${\displaystyle n\geq n_{0}}$

IS: n → n + 1: Since it has been shown for an n ₀ that T (n) ≤ c⋅n ³ ln ² (n) is correct and that c can be a constant of any size, the conjecture is correct. (A constant c ≥ 4 is sufficiently large for all n.)

Hence for T (n) it follows:   ${\displaystyle T(n)\in O(n^{3}\ln ^{2}(n))}$