Question

Consider the following algorithm that operates on a list of n integers:

• Divide the n values into n 2 pairs

• Find the max of each pair.

• Repeat until you have the max value of the list

(a) Show the steps of the above algorithm for the list (25,19,9,8,2,26,21,26,31,26,3,14).

(b) Derive and prove a tight bound on the asymptotic runtime of this algorithm

(c) Assuming you just ran the above algorithm, show that you can use the result and all intermediate steps to find the 2nd largest number in at most log2 n additional steps

Answer 1

The algorithm to find a maximum element in a list of values is shown as follows:

1. Divide the n number of values of the list into n/2 pairs.
2. Determine the maximum of each pair.
3. Repeat part 2 till the maximum element of the list is not found.

(a)

The steps of the given algorithm for the list (25, 19, 9, 8, 2, 26, 21, 26, 31, 26, 3, 14) can be shown as follows:

Step 1: Divide the n values of the list into n/2 pairs.

Step 2: Determine the maximum of each pair.

25 19, 9 8, 2 26, 21 26, 31 26, 3 14

   25     9     26       26       31      14

Step 3: Repeat step 2 till the maximum element is not found.

• The maximum of 25 and 9 is 25.
• The maximum of 26 and 26 is 26.
• The maximum of 31 and 14 is 31.

The resulted values will be as follows:

25       26         31

     26               31

               31

The last element which is 31 is the maximum element of the given list. The total number of steps which are used to find the maximum element is 12 i.e., the number of elements of the list.

Hence, the total number of steps to find a maximum element of the list is equal to the number of values in a list.

(b)

The tight bound on asymptotic runtime of the given algorithm can be derived and proved as follows:

The asymptotic runtime of the given algorithm can be found as follows:

Since the number of steps to get the maximum element of the list is equal to the number of elements of the list. Therefore, the runtime of the algorithm will be O(n).

The recurrence relation for this runtime can be formed as follows:

T(n) = 0, for n = 1

T(n) = 1, for n = 2

T(n) = T(n/2) + T(n/2) + 2, for n > 2

The value n in the above relation can be a power of 2.

The above relation can be written in general terms as follows:

T(n) = 2T(n/2) + 2

        = 2[2T(n/2)/2 + 2] + 2 => 4T(n/4) + 6

        = 4[2T(n/4)/2 + 2] + 6 => 8T(n/8) + 14

        .

        .

        .

        = 2^k-1T(2) + ∑(1≤i≤k-1) 2^k

        = 2^k-1 + 2^k – 2

        = 3n/2 – 2 (since n = 2^k)

T(n) = O(n)

Hence, the tight bound on the runtime of the given algorithm is O(n).

(c)

If an element of a list needs to be selected as maximum element of the list, then it must be compared with second maximum element of the list at some level of the comparison tree made in the part a.

The number of times the maximum element of the list is compared will be equal to the number of elements that needs to be checked for second maximum element.

So, the number of times the maximum element compared in the list will be height of the comparison tree formed in part a i.e., log₂n.

The elements from which maximum element found in part a is compared are 26, 14, and 26. Out of these three elements the maximum is 26. Therefore, the second maximum element of the list is found as 26.

The maximum number of elements by which the maximum element of the list found in part a will be compared cannot be more than log₂n.

Since the number of comparisons to find the maximum element in a list is equal to the number of elements of the list. Therefore, additional steps required to determine the second maximum element of the list is at most log₂n.