Question 2 [10 marks]
Consider the following algorithm which searches for the last appearance of value k in an array A of
length n. The index of the array starts from 0.
def FindLast(A, k):
1. for i= n-1 downto 0: #range bounds are inclusive
2. if A[i] == k:
3. return i
4. return “not found”
The input array A is generated in the following specific way: for A[0] we pick an integer from
{0, 1} uniformly at random; for A[1] we pick an integer from {0, 1, 2} uniformly at random; for A[2]
we pick an integer from {0, 1, 2, 3} uniformly at random etc. That is, for A[i] we pick an integer from
{0, . . . , i+1} uniformly at random. All choices are independent from each other. You can assume that
k is an integer whose value satisfies 1 ≤ k ≤ n and k is chosen uniformly at random from {1, …n}.
Analyse the complexity of FindLast by answering the following questions:
1. In the best case, how many times is Line #2 executed? Justify your answer.
2. What is the probability that the best case occurs? Show your work and explain your calculations.
3. In the worst case, how many times is Line #2 executed? Justify your answer.
4. What is the probability that the worst case occurs? Show your work and explain your
calculations. HINT: For every index in the array, is the probability of k being there the same
across all indices?
5. In the average case, how many times is Line #2 expected to be executed? Justify your answer
carefully: show your work and explain your calculations.
Give exact counts and probabilities in terms of n and k (not simply an asymptotic expression).When
applicable, write P using the the probability mass function convention from Week 2 Module.
3