In this task, we want to find a smallest element in an unordered array.

(b) Consider Algorithm B. Algorithm 1: Algorithm B Input: array a[1..n] Output: the position of a smallest element minPos = 1 j=1 while j a[j + 1] then L minPos = j +1 j=j +1 return min Pos i. (1 point) Formulate an invariant depending on a, j and minPos. Use the invariant to argue that the algorithm is correct. ii. (1 point) How often does the algorithm compare two elements of a (that is, a[minPos] > a[j]) in dependence of n in the worst case? Further, suppose that the running time depends only on comparing two elements of a. Further suppose that your computer can compare two elements of a in one millisecond. What is the worst case running time of the algorithm for n= 1000 000 on your computer? (c) (1 point) Discuss why any algorithm needs at least n - 1 comparisons to find a minimum element in the worst case