Substitution Method for Recursive Complexities

Method §

Basic method §

This method uses induction to prove solutions to Recursive Complexity Definitions. As such, it follows the typical inductive structure:

• Base case: show that the inequality holds for small $n$.
• Inductive step: substitute formula into recurrence and rearrange to obtain solution.

As this method can only prove a recurrence relation and not obtain a novel solution, it can only be used in instances where it is possible to make a good guess for the formula. This requires experience but can be made easier with heuristics.

Changing variables §

Sometimes a variable substitution can be used to transform a recurrence relation into something similar to a familiar formula. For example, given

$$T(n)=2T(\sqrt{n})+\log n$$

we can let $m=\log n$ ($\therefore n=2^m$), and substitute to obtain

$$T(2^m)=2T(2^{\frac{m}{2}})+m$$

This gives us the relation

$$S(m)=2S(\frac{m}{2})+m$$

which has the known solution of $O(m\log m)$. Undoing the substitution yields a solution for $T(n)$ of $O(\log n\log (\log n))$.

Selecting substitution §

Given a formula $T(n)$ containing the recursive term $T(f(n))$, a substitution $m=g(n)$ should be made such that $f(g^{-1}(n))$ is of the form $\frac{an}{b}$ for integers $a$ and $b$. Common substitutions include:

• $\sqrt{n}\to \log n$
• More generally, $n^{\frac{1}{k}}\to \log n$ for $n\in \mathbb{N}$

Example §

Given the recurrence equation $T(n)=2T(\lfloor \frac{n}{2}\rfloor )+n$, we can apply the substitution method to prove that this is equivalent to $T(n)\le cn\log n$:

Base case §

• When $n=1$, $cn\log n=0$.
• When $n=1$, $2T(\lfloor \frac{n}{2}\rfloor )+n=1$, so it does not hold for $n=1$.
• When $n=2$, $cn\log n=2c$.
• When $n=2$, $2T(\lfloor \frac{n}{2}\rfloor )+n=2$, so it does hold for $n=2$.

Inductive step §

Substituting $cn\log n$ into the recursive definition of $T(n)$ gives $T(n)=2(c\lfloor \frac{n}{2}\rfloor \log \lfloor \frac{n}{2}\rfloor )+n$. This can be rearranged in several steps:

• $=cn\log \frac{n}{2}+n$
• $=cn(\log n-\log 2)+n$
• $=cn\log n-cn+n$ As $cn+n>0\forall c>0$, this can be rewritten as: $T(n)\le cn\log n$.