Problem $3($Finding Max & $2$nd$-$Max using D&C$).$

In this problem, you are given a partial pseudocode for the problem of finding the maximum and

second$-$maximum in an array of $n$ distinct integers. Note that the naive algorithm solves this in

$2n-3$ comparisons. We will assume that $n=2^l$ is a power of $2(eg,2,4,8,16,$dots$).$ Your goal is to fill

in the blanks so that the code works correctly, and then answer questions regarding the number of

comparisons it makes. We are only interested in comparisons between array elements; so checking

if length is $2$ is not a comparison we are counting.

procedure MAX$-$AND$-2$ND$-$MAX $(A)$ :

$$ Returns tuple with first entry max and second entry $2$nd max of $A$

$$ Assumes the list has $2^k$ distinct integers for some integer $k1.$

if len$(A)=2$ then:

return

else:

Pair the elements $(A[1],A[2]$ and so on$.$

For every element einA, dictionary partner $(e)$ returns the element $e$ is paired with.

Blarr empty list.

Compare $e$ and partner$(e)$ for every einA, and append the larger element to $B.$

$$ You count the $($e$,$partner $(e))$ comparison only once. For instance, $A[2]$ is $A[1]\text{'}$s partner

and vice$-$versa. But you don't compare their comparison twice.

$13$:

$(b_1,b_2)larr$ MAX$-$AND$-2$ND$-$MAX $(B).$

return

a$.$ Fill the blanks in Line $5$ and in Line $6.(2$ points$)$

b$.$ Fill the blanks in Line $14$ and Line $15$ such that the algorithm works correctly. $(3$ points$)$

Let $T(n)$ be the number of comparisons made when the above algorithm is passed a list $A$ of $n=2^l$

distinct numbers. Note, all other operations are immaterial for $T(n).$

Clearly write the recurrence inequality governing $T(n).$ Write the base case and be exact: do not

use the big$-$Oh notation. Using the kitty method, solve the recurrence exactly for $n=2^l$ for some

positive integer $l1.$ We are interested in the exact answer as a function of $n,$ so express care. $(5$

points$)$