substitution method

Consider:

\begin{equation} T\qty(n) = 2 T\qty(\frac{n}{2}) + n \end{equation}

We can get the recurrence relation.

guess the answer

We can try to expand the middle by plugging stuff in:

  • \(T\qty(n) = 2T\qty(\frac{n}{2}) +n\)
  • \(T\qty(n) = 2\qty(2 T\qty(\frac{n}{4})+ \frac{n}{2}) + n\)
  • \(T\qty(n) = 4T\qty(\frac{n}{4}) + 2n\)
  • …

We can guess the pattern by staring at it: \(T\qty(n) = 2^{j} T\qty(\frac{n}{2^{j}}) + j\cdot n\) is true for all \(j\).

Suppose \(j= \log \qty(n)\) (that’s where \(T\qty(n)\) disappears), \(T\qty(n) = n\qty(\log \qty(n) + 1)\).

prove the guess is correct

  • inductive hypothesis: \(T\qty(n) = n\qty( \log\qty(n) + 1)\)
  • base case: \(T\qty(1)\) given to you
  • inductive step: use strong induction as \(n\) get smaller

and then finally state you guess.

example

Consider the following fun recurrence relation:

\begin{equation} T\qty(n) \leq T\qty(\frac{n}{5}) + T\qty(\frac{7n}{10}) + n, n > 10 \end{equation}

base case where \(T\qty(n)=1\), when \(1 \leq n \leq 10\). Let’s try to use the substitution method to solve this.

Guess

By divine guess we guess \(O\qty(n)\).

Induction

Recall that our inductive hypothesis cannot be \(T\qty(n)=O\qty(n)\), because we will have extra quantifiers for all \(n\) instead of a specific \(n\). Our inductive hypothesis has therefore be more specific, namely:

Inductive hypothesis:

\begin{equation} T\qty(n) \leq Cn \end{equation}

Base case: \(1 = T\qty(n) \leq Cn\) for all \(1 \leq n \leq 10\) as per given.

Inductive step:

For \(k > 10\), assume that IH holds (strong) for all \(n\) such that \(1 \leq n < k\).

\begin{align} T\qty(k) &\leq K + T\qty(\frac{k}{5}) + T\qty(\frac{7k}{10}) \\ &\leq k + C\qty(\frac{k}{5}) + C\qty(\frac{7k}{10}) \\ &= k + \frac{C}{5}k + \frac{7C}{10} k \end{align}

So we desire \(C\) such that:

\begin{equation} k + \frac{C}{5}k + \frac{7C}{10} k \leq Ck \end{equation}

solving for \(C\), we note that:

\begin{equation} 1 \leq \frac{C}{10} \end{equation}

will hold for this equation.

Conclusion so there is some \(C=10\) such that for all \(n \geq 1, T\qty(n)\leq Cn\).