============================================================================
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.