Skiena 2-45

[mykola-den]

Consider the following algorithm to find the minimum element in an array
of numbers A[0,...,n]. One extra variable tmp is allocated to hold the current
minimum value. Start from A[0]; ”tmp” is compared against A[1], A[2], ..., A[N]
in order. When A[i] <tmp, tmp = A[i]. What is the expected number of times that
the assignment operation tmp = A[i] is performed?