Solving Recurrences using Iteration Method

Last Updated on 5 years ago by ICT Byte

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