Question $1.$

$($a$)$ Solve the following recurrence using iterative substitutions:

$T(2)=1,T(n)=2T(\frac{n}{2})+c$

where $c>0$ is a constant. You can assume $n=2^k$ for some integer $k.$

$[8$ marks$]$

$($b$)$ The algorithm MaxMax $($given below$)$ finds the maximum and second maximum elements of an array. For example, if the array is $S=[1,7,9,6,5]$ then the maximum is $9$ and the second maximum is $7.$ This algorithm calls another algorithm Compare, also given below. Write down the exact number of comparisons made by Compare. Also write down the recurrence $T(n)$ expressing the time complexity of MaxMax $($count only the number of comparisons between elements of $S).$ Solve this recurrence using Part $($a$).$

$[6$ marks$]$