============================================================================
CSC 263 Tutorial 1 Winter 2019
============================================================================
Consider the following algorithm to find the maximum element in a list.
FIND-MAX(L):
max = -oo # minus infinity
for k = 0 to len(L)-1:
if L[k] > max:
max = L[k]
return max
For this problem, we are interested in the number of times that variable max
gets assigned a value.
1. What is the average-case number of times that max is assigned a value by
algorithm FIND-MAX? Show your work -- in particular, define your sample
space and probability distribution clearly, show the steps in your
computation, and simplify your final answer.
2. What is the best-case number of times that max is assigned a value by
algorithm FIND-MAX? Show your work.
3. What is the worst-case number of times that max is assigned a value by
algorithm FIND-MAX? Show your work.