Consider the following java algorithm for the problem of deciding whether two arrays A, B, each of size n, have common values.

i. Prove that this algorithm is correct by showing the following:

a. Show that the algorithm terminates.

b. Show that the algorithm always produces the correct answer. First state what needs to be proven: If A and B have at least one common value then the algorithm must ... If A and B have no common values then the algorithm must ... . Then show that the algorithm always produces the correct answer.

ii. Explain what the worst case for the algorithm is.

iii.Compute the time complexity of the algorithm in the worst case. You must give the order of the time complexity and explain how you computed the time complexity.

Algorithm haveCommon(A, B, n) Input: Arrays A and B each storing n integer values. Out: true if A and B have at least one common value; false otherwise. for it to n - 1 do { j=0 while j