Let A and B be two sorted arrays, each with n elements. You have to write an efficient algorithm which finds out if A and B have any elements in common. For example if A = [4, 7, 12, 15], B = [2,4,6,23000] the answer should be yes (since 4 is an element in common), if A = [4, 7, 900], B = [2,3, 28] the answer should be no. In terms of efficiency, the faster your algorithm is, the better.

You will get full credit if your algorithm is correct and works in time O(n).

You will get substantial partial credit if your algorithm is correct and works in time smaller than O(n 2 ) but bigger than O(n).

You will get some partial credit if your algorithm is correct and works in time O(n 2 ).

(a) Give a very short and clear description in English of the basic idea behind your algorithm.

(b) Give the pseudocode (c) Trace your algorithm on the above two examples.

(d) Do a worst case time analysis (use big O notation) of your algorithm. No explanation necessary.