StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q1SE

Expert-verifiedFound in: Page 233

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 $({a}_{1},{a}_{2},\dots {a}_{n}":\mathrm{integerswith}"n\ge 2)$

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

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

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" $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

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

94% of StudySmarter users get better grades.

Sign up for free