Consider the algorithm foo, described in pseudocode below, and answer the follow
ID: 3803008 • Letter: C
Question
Consider the algorithm foo, described in pseudocode below, and answer the following questions. Algorithm foo (A, n, B, m) Input: arrays of integers, A of length n and B of length m output: true or false for i = 0 to n - 1 for j: = 0 to m-1 if A[i] == B[j] return true endif endfor endfor return false (a) Explain, in words, what algorithm foo does (i.e. give a high-level account of what is computed, not a blow-by-blow description of the code). (b) Provide an analysis of the run-time complexity of foo. You should express your analysis using big-0 notation and justify your answer. (c) Suppose that you know in advance that the integer arrays A and B are sorted in ascending order. Write a new algorithm baz that does the same as foo, but uses the fact that A and B are sorted to achieve better run-time complexity than foo. Present pseudocode for your algorithm and an argument that it has better run-time complexity than foo.Explanation / Answer
a)The algorithm returns true for every match in the number.
For every digit in A , it checks if the same number is in B and returns TRUE, else it goes to next Number in B till the end of array B(mth element). After it reaches end of B, it continues the same process till end of A,i.e., nth element in A. It even returns FALSE if there isn’t any common element in both arrays.
b)We have two FOR loops For every element in A starting from 1st to nth element in A ,Another FOR loop executes for ‘m’ iterations and in each iteration we have an IF expression
Let’s say the inner FOR loop takes ‘2n’ time units. So ,for ‘n’ elements in A it takes n(2n)=2n2 ~ n2 units ,i.e., in the big-O notation the time complexity is O(n2 )
c)If both the arrays are sorted, then for an element in A say ‘x’ ,We can compare in B only till we are going through the numbers less than ’x’ in B.
Say A={3,5,7,9}
B={1,2,4,7,9}
Here for first element in A ,A[0]=3, We search in B till B[2]=4 only ,because the arrays are sorted we will not get number more than ‘3’ after B[2]=4.
So, the algorithm goes like this.
-------------------------------------
For i:=0 to n-1
For j:=0 to m-1
If A[i]==B[j]
Return true
endif
If A[i]<B[j]
continue
else
break
endif
endfor
endfor
return false