I’d like to find the average number of comparisons for finding ALL minimum values in an array.

The code would look something like this:

let all_min = [(0, vec[0])]
let cur_min = vec[0]

for i in 1..vec.len() {
  if vec[i] == cur_min {
    all_min.push((i, vec[i]))
  } else if vec[i] < cur_min {
    cur_min = vec[i]

    all_min.clear()
    all_min.push((i, vec[i]))
  }
}

In the best case, the entire array will be one value. Thus, the second if statement will never be explored and only n – 1 comparisons will be made.

In the worst case, the array will be a reversed sorted array. Thus, the second if statement will ALWAYS be explored and 2 * (n – 1) comparisons will be made.

However, I’m really struggling to calculate the average number of comparisons made. If anybody could walk me through the process, that would be amazing.