Iteration Method

The iteration method is the most naive, brute-force method for solving recurrences. This is done by rewriting the right hand side until we see a pattern forming

Examples

$T(n)=T(n/2)+1$

$T(n)=T(n/2)+1=T(n/2^j)+{\sum }_{i=1}^{j}1=T(n/2^j)+j=lg(n)$ The reason it becomes lg(n) is because we usually have an inital condition, for example $T(1)=1$. Our recurrence stops at this point, and we can find it by $n/2^j\le 1$ → $lg(n)\le j$