• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q1SE

Expert-verified
Found in: Page 233

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# 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.

(a) procedure last largest $\left({a}_{1},{a}_{2},\dots {a}_{n}":\mathrm{integerswith}"n\ge 2\right)$

$max:={a}_{1}$

$position:=1$

for $i:=2$ to n

if ${a}_{i}>max$ then

$max:={a}_{1}$

$position:=1$

return position

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

See the 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 $\left({a}_{1},{a}_{2},\dots {a}_{n}:integerswithn\ge 2\right)$

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

## Step 2: Algorithm

Combining these steps, we then obtain the algorithm:

procedure last largest $\left({a}_{1},{a}_{2},\dots {a}_{n}:integerswithn\ge 2\right)$

role="math" localid="1668488545991" $max:={a}_{1}\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}position:=1\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}fori=2ton\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}if{a}_{i}\ge maxthen\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}max:={a}_{1}\phantom{\rule{0ex}{0ex}}\phantom{\rule{0ex}{0ex}}position:=1$

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)$ .