(a) Describe an algorithm for finding the second largest integer in a sequence of distinct integers.
(b) Give a big- $O$ estimate of the number of comparison used by your algorithm.

Question

Quizplus · Accepted Answer

The Answer is (a) We first compare the first and second integers in the sequence

a _ { 1 } , a _ { 2 } , \ldots , a _ { n }

, setting the value of the variable firstmax equal to the larger, and the value of the variable secondmax equal to the smaller. For each successive integer

a _ { i }

in the sequence,

i = 3,4 , \ldots , n

, we first compare it to firstmax. If

a _ { i } >

firstmax, then we make the assignments secondmax

: =

firstmax and firstmax

: = a _ { i } .

Otherwise, we compare

a _ { i }

to secondmax, and if

a _ { i } > \operatorname { secondmax }

, then we make the assignment secondmax :=

a _ { i }

. At the end of this procedure the value of secondmax will be the second largest integer in the sequence.
(b) We do one comparison at the beginning of the algorithm to determine whether

a _ { 1 }

or

a _ { 2 }

is larger. Then for each successive term, for

i = 3,4 , \ldots , n

, we carry out at most two comparisons. Hence the largest number of comparisons used is

2 ( n - 2 ) + 1 = 2 n - 3

, ignoring bookkeeping. This is

O ( n )

.

(A) Describe an Algorithm for Finding the Second Largest Integer OOO

(A) Describe an Algorithm for Finding the Second Largest Integer $O$