Iteration Method
- Expand the relation so that summation dependent on n is obtained
- Bound the summation
Example
T(n)=2T(n/2)+1
T(1)=1
Solution:
T(n)=2T(n/2)+1
Let there is k iteration. So, for the first iteration, k=1. K=2 represents second iteration and goes on.
Let’s find what is T(n/2)
For this, put it in original function T(n)
i.e Replace n with n/2.
Now the further step gives,
T(n/2)=2T(n/2)/2)+1
= 2T(n/4)+1
For second iteration, i.e k=2
T(n)=2T(n/2)+1
=2(2T(n/4)+1)+1
=4T(n/4)+2+1
Now, we need to find what is T(n/4)
Replace n with n/4 in T(n)
It gives,
T(n/4)=2T(n/4)/2+1
= 2T(n/8)+1
For third iteration, i.e when k=3
T(n)=4T(n/4)+2+1
= 4(2T(n/8)+1]+2+1
=8T(n/8)+4+2+1
Again, we need to find T(n/8)
Replace n with n/8
It gives T(n/8)=2T(n/8)/2+1
=2T(n/16)+1
For forth itera++tion, i.e when k=4
T(n)=8T(n/16)+4+2+1
=
Which can be generalised as
T(n) = 2^k * T(n/ (2^k) )+ 2 *(2^k — 1)
T(n) = 2^k * T(n/ (2^k) )+ 2^(k+1) — 2
……
2^k*T(n/(2^k)+Summation from i=0 to k-1 [2i]
To be continued.. check note
