1 Solve the following recurrence relation in terms of n assu

1)          Solve the following recurrence relation in terms of n assuming n=2^k

W(n) = 2 W(n/2) + n/2

W(1)=0

Explain with answer.

Solution

W(n)= 2W(n/2)+n/2

W(n/2)= 2W(n/4)+n/4

W(n)= 2(2W(n/4)+n/4)+n/2

W(n)= 4W(n/4)+n/2+n/2

W(n/4)= 2W(n/8)+n/8

W(n)= 4(2W(n/8)+n/8)+n/2+n/2

W(n) = 8W(n/8) + n/2+n/2+n/2

This process continues till when we reach W(1) and here we are seeing that it is decresing exponentially by a factor of 2. So to reach 1 we need the W(n/n), Initially it was W(n/2¹) In the next iteration it becomes W(n/2²). Later it becomes W(n/2³). So, in this way when it becomes W(n/n)

Therefore n=2ⁱ

So, i=log₂ n steps it becomes equal to n and later on we are seeing n/2 term in each iteration, so it will go till logn steps. Thus complexity is O(nlogn)