Question

a) Describe an algorithm for finding the first and second largest elements in a list of integers.

b) Estimate the number of comparisons used.

Short answer

(a) procedure last largest $(a_1,a_2,\dots a_n:integerswithn\ge 3)$

if $a_1<a_2$ then

$max:=a_2$

$next:=a_1$

else

$max:=a_1$

$next:=a_2$

for $i:=3$ to n

if $a_i\ge max$ then

$next:=max$

$max:=a_i$

else if$next\le a_i<max$then

$next:=a_i$

returnlast,next

(b)$2n-1,O\left(n\right)$

Step-by-step solution

Step 1

(a) $\ text {\color{\# 4257 b 2} Let us call the algorithm "two largest" and the input of

the algorithm is a list of integers $a_1,a_2,\dots ,a_n$ \color\{default }

\ \

\ textbf\{procedure \}two largest $(a_1,a_2,\dots a_n$ integers with $n\ge 3$)

\ \

\color{4257b2}The variable “max” will keep track of the largest number, while “next”

Will keep track of the second largest number. We initially define the first two

elements in the list as these two variables (largest of the two is “max” , while

smallest is “next”, if equal, then both values are set to the values).\color{default}

\ \

\textbf{if} $a_1<a_2$\textbf{then}

$max:=a_2$

$next:=a_1$

\textbf{else}

$max:=a_1$

$next:=a_2$

\ \

\color{#4257b2}Next we compare every ( other) element in the list with the current

Largest number. if the element is larger than or equal to the current largest

number, then we replace the maximum by this element and we move the old

maximum to second largest element\

Next, we also determine if the element if between the second largest and the

Largest element(up to now ). If this is the case, then we replace the second highest

element by this new element\color{default}

\ \

\textbf{for}i=3\textbf{to}n

\textbf{if}$a_i\geq$max\textbf{then}

$next:=max$

$max:=a_1$

\textbf{else if}$next\le a_i$ <max\textbf{then}

$next:=a_1$

\ \

\color{#4257b2} Finally, we return the position of the two largest

numbers.\color|{default}

\ \

\textbf{return } last, next}$

Step 2

Combining these steps, we then obtain the algorithm: Procedure last largest

$(a_1,a_2,\dots a_n:integerswithn\ge 3)$

If $a_1<a_2$then

$max=a_2$

$next:=a_1$

else

$max:=a_1$

$next:=a_2$

for $i:=3$ to n

if $a_i\ge max$then

$next:=max$

$max:=a_i$

else if$next\le a_i<max$ then

$next:=a_i$

returnlast,next

Step 3

(b) We note that the algorithm initially makes 1 comparison to check $a_1<a_2$

Next, the algorithm makes at most two comparison ( $a_i\ge max$and $next\le a_i<max$)

In every iteration of the for –loop. Since i ranges from $3ton$, there are

$n-3+1=n-2$ iteration of the for –loop and thus there are $2(n-1)$comparison in

for –loop.

We then note that there are $2(n-1)+1=2n-2+1=2n-1$comparison in total, while

$2n-1isO\left(n\right)$.