(a) Write a recurrence relation for the eract (worst case) number of key comparisons, i.e., comparisons between keys of list elements, done by the following algorithm. Your recurrence should be expressed in terms of n, the number of elements in the list Assumenfo the appropriate b. Be sure to include a base case. The algorithm doesn't necessarily do anything useful. REC(L) is D returns a (possibly) modified version of L D Initial call is to REC(L), where L is a list; |L is the number of elements in L if IL| 3 1 then return L endif L1 = first IL|/2 elements of L L2 = last | LI/2 elements of L L, = REC(L1) 2 REC(4) L, = REC(Li) D not a key comparison while |Li-0 and | Lal0 do if FIRST L1) > FIRST L2) then else endif no key comparisons here REST(L2) REST(LI) , FIRST(2) + L'; L2 , FIRST(1)+L'; L1 return L' end REC (b) Give a bound for your recurrence in part (a)