Skip to content

Subsitution method

The Subsitution method

For a function \(T(n)\) satisfying some recurrence relation

\[ T(n)=a_1T(b_1n)+\dots+a_kT(b_kn)+f(n), \]

we can guess a bound for \(T(n)\), then use mathematical induction to show the bound holds for each \(n\).