Consider the following algorithm // L is a list and n is its length // For the purpose of this assignment we assume that n= 4**k , for k1 //

Considerthefollowingalgorithm

//Lisalistandnisitslength

// Forthepurposeofthisassignmentweassumethatn=4**k,fork≥1

// Alg1(L,n)

removethesmallestandlargestelement fromL

if n-2 >(4**k)/2

call Alg1(L, n-2)

a) Whatisthealgorithmintendedtodo?

b) Isitcorrect? Ifitisnotcorrectdiscovertheerror(s)whentryingtoprove correctnessandfixit(them). Then,reprovethecorrectness.

c) Whatisitstimecomplexity?

d) Canitbeimproved? Youmayuseanyalgorithmdiscussedinclass.