Consider the algorithm foo, described in pseudocode below, and answer the follow

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

                               

      

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.