---
title: "substitution method"
type: concept
related: [Substitution Method]
source: https://www.jemoka.com/posts/kbhsubstitution_method/
confidence: high
status: active
---

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\) &hellip; 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&rsquo;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 &gt; 10 \end{equation}
base case where \(T\qty(n)=1\), when \(1 \leq n \leq 10\). Let&rsquo;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 &gt; 10\), assume that IH holds (strong) for all \(n\) such that \(1 \leq n &lt; k\).
\begin{align} T\qty(k) &amp;\leq K + T\qty(\frac{k}{5}) + T\qty(\frac{7k}{10}) \\ &amp;\leq k + C\qty(\frac{k}{5}) + C\qty(\frac{7k}{10}) \\ &amp;= 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\).
