Question

Solve the following recurrence relation, subject to the basis. S(1) = 2 S(n) =2S(n/2) + 2n

Answer 1

Solutions:-

given

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

now we are consider that

S(n)= 2 , n=1

S(n)=2S(n/2)+2n ,    n>1   

S(n)=2S(n/2)+2n --------------------(1)

S(n/2)=2S(n/2²)+2*(n/2)

=2S(n/2²)+n

put the value of S(n/2) on equation (1).

S(n)=2[2S(n/2²)+n]+2n

=2²S(n/2²)+2n+2n

S(n) =2²S(n/2²)+4n-------------------(2)

S(n/2²)=2S(n/2³)+2*(n/2²)

=2S(n/2³)+(n/2)

S(n)=2²[2S(n/2³)+(n/2)]+4n

S(n) =2³S(n/2³)+6n-------------------(3)

|

|

|

|

S(n)=2^kS(n/2^k)+2kn (using K term)

2k is constant so we can write it as only k

S(n)=2^kS(n/2^k)+kn

let we are assume that

S(n/2^k)=S(1)

n/2^k=1

or,n=2^k

or,k =log n

now,

S(n)=n*1+n(log n)

time complexity=O(n log n)