(a) Use a divide-and-conquer approach to devise a procedure to find the largest and next-to-largest numbers in a set of n distinct integers.
(b) Give a recurrence relation for the number of comparisons performed by your procedure. (Make sure to include the initial conditions)
Workings:
a. Suppose that $n$ is a set of distinct integers.
Suppose than $n$ is an even number.
Assume that the largest $L1$ and second largest $l1$ in the first half on n is already known
Further assume that the largest $L2$ and second largest $l2$ in the second half of n is also known
Then make the following two comparison
$L1$ and $L2$
$l1$ and $l2$
This is to find $L$ the largest of the set.
Now compare the smaller of the $L$ with the winner of the $l1$ and $l2$ to find the second largest $l$
However if $n$ is odd we split $n$ into almost half.
I'm not sure if this is correct. And I don't know part b. Any help will be appreciated.
For your recurrence relation, you have $T(n) = 2T(n/2) + C$ when $n$ is even, for some constant $C$, and you have $T(n) = T(n/2 + 1/2) + T(n/2 - 1/2) + C$ when $n$ is odd. Depending on how demanding your grader will be, you may have to determine the exact number of operations that determine $C$, as well as defining $T(3)$ and $T(2)$.