1. The following algorithm returns true if the sorted array A contains all unique elements (no duplicates) and returns false otherwise:

ALL_UNIQUE(sortedA)

for i = 1 to sortedA.length-1

if sortedA[i] == sortedA[i+1]

return false

return true

a. Write a loop invariant that can be used to prove the correctness of the algorithm.

b. Show that the loop invariant is true at the initialization of the loop.

c. Show the that loop invariant is true during the maintenance of the loop

d. Show that the loop invariant is true at the termination of the loop and show that the algorithm computes the correct output.

e. Using the cost constants c₁, c₂, shown for each line of pseudocode above, give an expression for the number of times each line is executed (fill in to the right of the code), and an expression for the total cost of executing this function