Question $11$

Suppose you are given arrays big $[]$ and huge $[],$ each containing distinct numbers $($ie$,$ they have no re$-$

peated numbers$).$ Both arrays are unordered $($ie$,$ they are not sorted$).$ Further, suppose that big $[]$ is much

smaller than huge $[]($for example big. length $=10,000$ and huge $.$ length $=10,000,000,000,000.)$

Design an algorithm to determine how many numbers there are in common between the two arrays. In

the worst case, your algorithm must run in time proportional to huge. big.length$).$

Write your algorithm in Java. You may use any algorithms or data structures that we have discussed

in class, without defining them. For example, you can create a Stack or a MinPQ. You can also as$-$

sume that you have access to algorithms implemented on arrays, such as swap, swim, heapSort, and

binarySearch, with reasonable parameter and return types. $($Hint: Given that the worst case running

time must be huge. length $log($big$.$ length$)$ or better, you call heapSort on big, but not huge.$)$

For each operation, make sure it is clear which array you are working on: big $[]$ or huge $[].$

Be sure to include a return statement, to return the result.