Please I want complete answer for analysis of algorithms question!? When parent\
ID: 3677304 • Letter: P
Question
Please I want complete answer for analysis of algorithms question!? When parent's key becomes smaller than one (or both) of its children in Heap, the sink method is called. The iterative algorithm for the sink method is given below: a) Convert the above algorithm to a recursive algorithm. b) Write a recurrence relation that computes the worst case running time for your recursive algorithm. c) Use the maser method to approximate the order of the worst case running time of your recursive algorithm.Explanation / Answer
sink(list,k,key,bound)
{
if(largerChild<bound)and (list[largerChild+1]>list[largerChild])
{
return exch(larger Child, larger Child+1);
}
else if
key>list[largerChild]
break;
exch(k,largerChild);
else if
2*k<=bound
retun exch (larger Child,2*k);
else
return 1;
b)recursion relation is 4T(n)+1 i.e for first exchane n+1 second exchane n third exchange 2n so 4n+1
ie worst case complexity is O(n)
c)maser theorm is aT(n/b)+(nklogpk) and according to theorm conditions are a>=1,b>1,k>=0,and p is real number here a=4 ,b=1 so does not satisfied