Let A and B be two non-sorted arrays. Assume that all the numbers in A are pairw

Question

Let A and B be two non-sorted arrays. Assume that all the numbers in A are pairwise disjoint and the same is true for B. Write an efficient as you can algorithm that lists all the elements (values) of B that that do not appear in A. Example: A = [4, 2, 5, 3, 7, 1], B = [13, 7, 4, 21, 5, 3]. The values of B that do not appear in A are 13, 21.

In the algorithm, always explain how and why they work. ALWAYS, analyze the complexity of an algorithm. In all algorithms, always try to get the fastest possible.In all data structures, try to minimize as much as possible the running time of any operation.

Explanation / Answer

STEP 1: I=0

STEP 2: REPEAT STEPS 3 - 9 UNTILL I<6

STEP 3: LOC =-1

STEP 4: J=0

STEP 5 REPEAT STEPS UNTILL J<6

STEP 6: IF B[I] = A[J] THEN LOC =J EXIT AND GOTO 8

STEP 7: J=J+1 GOTO 5

STEP 8: IF LOC =-1 THEN DISPLAY B[I]

STEP 9: I=I+1: GOTO 2

STEP 10 : STOP

IN WORST CASES EVERY ELEMENT SHOULD BE COMPARED WITH 6 ELEMENTS i.e FOR TOTAL ELEMENTS 36 COMPARISIONS. BUT IT CAN BE DECREASED WHEN AN ITEM FOUND AT EARLY AND EXIT FROM INNER BLOCK

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

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