**Iterative Method**

- In this method we dont have to guess the answer but it require more algebra than the substitution method.
- Hence, the recurrence is expanded or iterated so that it can be expressed as the summation of its term depend only on n and the initial condition.

**P)**Solve T(n)=T(n/2)+1 if n>1

1 if n=1

*Solution:*

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

⇒T(n)=T(n/2²)+1+1

⇒T(n)=T(n/2^{k})+1+1.....+1

( Put n/2^{k}=1

⇒n=2^{k}

⇒k=log n)

⇒T(n)=1+k=O(k)=O(log n)

**P: 2**) Solve T(n)=3T(n/4)+n

**Solution**:

T(n)=3T(n/4)+n

⇒T(n)=n+3(n/4)+3T(n/16))

⇒T(n)=n+3T(n/4)+3^{2}T(n/4^{2})

⇒T(n)=n+3n/4+3^{2}(n/16+3T(n/64))

⇒T(n)=n+(3/4)n+(3/4)^{2}n+3^{3}T(n/4^{3})

⇒n+3n/4+3^{2}n/4^{2}+.....+3^{logn}ø(1)

⇒T(n)≤n+3n/4+3^{2}/4+.....+3^{logn}ø(1)

⇒T(n)≤n+3n/4+3²/4+....+n^{log3}

^{⇒T(n)≤n.4+O(n)}

⇒T(n)=O(n)