Question

a) Describe an algorithm for locating the last occurrence of the largest number 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":\mathrm{integerswith}"n\ge 2)$

$max:=a_1$

$position:=1$

for $i:=2$ ton

if$a_i>max$ then

$max:=a_1$

$position:=1$

return position

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

Step-by-step solution

(a)Step 1: Write algorithm

Let us call the algorithm "last largest" and the input of the algorithm is a list of

integers$a_1,a_2,\dots ,a_n$ .

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

The variable "max" will keep track of the largest number and then variable "position"

will keep track of the position of the largest number. We initially define the maximum

as the first element.

$max:=a_1$

$position:=1$

Next we compare every (other) element in the list with the current largest number. If

the element is larger than (or equal, since we are interested in the last occurrence)

the current largest number, then we replace the maximum by this element.

$fori:=2ton$

$if{a}_i\ge maxthen$

$max:=a_i$

$position:=i$

Finally, we return the position of the last occurrence of the largest number.

return position

Algorithm

Combining these steps, we then obtain the algorithm:

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

role="math" localid="1668488545991" $$\begin{gathered} max:=a_1 \\ position:=1 \\ fori=2ton \\ if{a}_i\ge maxthen \\ max:=a_1 \\ position:=1 \end{gathered}$$

return position

(b) Step 3: Number of comparisons

The algorithm only makes a comparison when $a_i\ge max$is executed, which

occurs in every iteration of the for-loop. Since can take on values from $2ton$,

there are $n-1$iterations of the for-loop and thus $n-1$comparisons are made, while $n-1isO\left(n\right)$.