[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/substitution_method.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- 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\) … 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\).