Question

Find a recurrence relation that describes the number of comparisons used by the following algorithm: Find the largest and second largest elements of a sequence of n numbers recursively by splitting the sequence into two subsequences with an equal number of terms, or where there is one more term in one subsequence than in the other, at each stage. Stop when subsequences with two terms are reached.

Short answer

The recurrence relation is

\(\begin{array}{l}f(n) = f(n/2) + f(n/2) + 2\\ = 2f(n/2) + 2\:\\{\rm{when}}\:n = {2^k}\end{array}\)

Step-by-step solution

Given data

Let \(f(n)\)represents the number of comparisons used by the algorithm described in the exercise prompt for a sequence of numbers.

Definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms.

Step 3:

We are interested in finding the largest and second largest element of a sequence ofnumbers.
Let \(f(n)\)represents the number of comparisons used by the algorithm described in the exercise prompt for a sequence ofnumbers.
We divide the list ofnumbers into two subsequence’s with\(n/2\)elements each.
We require\(\;f(n/2)\)comparisons for each subsequence.
To determine the two largest elements in the sequence ofnumbers, we need to first compare the two largest elements in the two subsequences (one comparison), next we compare the smallest element of the two with the second largest element in the other subsequence (one comparison) and then we should know which two elements are the largest in the entire sequence.

Thus, we make \(2\)more comparisons

\(\begin{array}{l}f(n) = f(n/2) + f(n/2) + 2\\ = 2f(n/2) + 2\:\\{\rm{when}}\:n = {2^k}\end{array}\)