10 pts) You are given two arrays of integers A and D, with A sorted in ascending
ID: 3746750 • Letter: 1
Question
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 i0 to length(A)-1 f # iterate through A # iterate through D # check pairwise for j 0 to length(D)-1 0 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 Ai, Di that will be the best case, and arrays A2, (c) Write pseudocode for an algorithm that runs in (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.Explanation / Answer
a. Let the length of Array A be m and the array D be n.
The worst case will be when the first loop runs for m times and the second loop runs for the n times. It means that the last element of the Array A matches the last element of the Array D.
Hence, the worst case complexity of the algorithm mentioned is O(m*n).
The example is shown in (b).
b. For n=4, the best case will be when the first element of A1 matches the first element of D1.
Array A1 = {4,5,6,7} // A is sorted in ascending order
Array D1 = {4,3,2,1} // D is sorted in descending order
Here, the first element matches and hence is the best case.
For n=4, the worst case will be when the last element of A2 matches the last element of D2.
Array A2 = {1,5,10,15} // A is sorted in ascending order
Array D2 = {100,30,20,15} // D is sorted in descending order
Here, the last element of A2 matches the last element of D2 and hence is the worst case.
c. Algorithm to find the common element in O(n) time.
// function which finds if there is a common element in array A and array D.
findCommonElement (A, D) :
\ initialize the index of Array A such that it points to its smallest element
i = 0;
\ initialize the index of Array D such that it points to smallest element
j = length(D) - 1;
// loop through the elements of A and D to find the match
// if i exceeds length (A) or j becomes less than zero, stop and return false.
while ( i < length(A) && j >= 0 ){
// compare the elements of A and D, if equal return True
if ( A[i] == D[j] ) { return TRUE }
// if the element of array A is smaller, increase the index to make it greater
else if ( A[i] < D[j] ) { i++ }
// if the element of arrat D is smaller, then decrease the index to make it greater
else if ( A[i] > D[j] ) { j-- }
}
// return false if nothing matches
return FALSE
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.