Algorithms & Pseudocode

2. (10 pts) You are given two arrays of integers A and D, with A sorted in ascending order and D sorted in descending order. Consider the following algorithm for checking whether or not A and D have an element in common. findCommonElement (A, D): # assume that A is sorted in ascending order and D is sorted in descending order for i-0 to length (A)-1 ( # iterate through A # iterate through D # check pairwise for j 0 to length(D)-1 { if (A[i] D [j]) { return TRUE } return FALSE (a) If arrays A and D have size n, what is the worst case running time of the procedure (b) For n 4, describe input arrays A, Di that will be the best case, and arrays A2, (c) Write pseudocode for an algorithm that runs in e(n) time for solving the problem. findCommonElement? Provide a bound. D2 that will be the worst case for findCommonElement Your algorithm should use the fact that A and D are sorted arrays