Substitution Method

A form of Recurrence Equations, where we:

1. Guess a solution
2. Suppose it is right for all $m<n$
3. Prove that it is correct given the assumption
   • Important to understand Asymptotic Notation here

How do i know if i guess wrong?

• A wrong guess will lead to a wrong equation (Remember that equations ($\ge and\le$) are strict!)

Examples

Merge-Sort

Merge sort has a run time of $T(n)=2T(n/2)+n$

Guess $T(n)=O(n\ast lg(n))$ Assume $T(m)\le c\ast m\ast lg(m)$, $m<n$

→ $m=\frac{n}{2}<n$ → $T(n/2)\le c\frac{n}{2}lg(n/2)$

insert this into our equation for T(n) → $T(n)\le cn\ast lg(n)-lg(2)\ast cn+n=cn\ast lg(n)$, QED