Consider the following algorithm for searching a list L of integers
for the element of maximum value:
function MAX (L[1:n])
input: L[1:n] (array of integer list elements)
output: The location max_element_location of the maximum
number in L
max_element_value := L[1]
max_element_location := 1
for j := 2 to n do
if L[j] > max_element_value then do the following:
max_element_value := L[j];
max_element_location := j
endif
endfor
return(max_element_location)

If L={1,2,3} then how many times does the value of
max_element_location change in MAX(L)?

Repeat for L={1,3,2}, L={2,1,3}, L={2,3,1}, L={3,1,2}, L={3,2,1}

From the first two parts above you have the number of times
max_element_location changes for each possible input list of three elements.
Summing all these numbers and dividing by 6 (the number of possible inputs)
gives the average number of times max_element_location changes for lists of
three elements. What is that number?

What is the average number of times max_element_location changes
for lists of four elements?

What is the average number of times max_element_location changes
for lists of eight elements? Do you see a trend?

Find a function f(n) which is the average number of times
max_element_location changes for lists of n elements.