Consider:

We can get the recurrence relation. guess the answer We can try to expand the middle by plugging stuff in: T\left(n\right) = 2T\left(\frac{n}{2}\right) +n T\left(n\right) = 2\left(2 T\left(\frac{n}{4}\right)+ \frac{n}{2}\right) + n T\left(n\right) = 4T\left(\frac{n}{4}\right) + 2n … We can guess the pattern by staring at it: T\left(n\right) = 2^{j} T\left(\frac{n}{2^{j}}\right) + j\cdot n is true for all j. Suppose j= \log \left(n\right) (that’s where T\left(n\right) disappears), T\left(n\right) = n\left(\log \left(n\right) + 1\right). prove the guess is correct inductive hypothesis: T\left(n\right) = n\left( \log\left(n\right) + 1\right) base case: T\left(1\right) 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:

base case where T\left(n\right)=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\left(n\right). Induction Recall that our inductive hypothesis cannot be T\left(n\right)=O\left(n\right), 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:

Base case: 1 = T\left(n\right) \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.

So we desire C such that:

solving for C, we note that:

will hold for this equation. Conclusion so there is some C=10 such that for all n \geq 1, T\left(n\right)\leq Cn.