Extract common elements btw two arrays

solution 1: pretty bad
complexity: O(sA x sB)
worst case: j goes to sB j goes to sB again... sAxsB
best case: sA

A, B


for i = 0 ; i < size(A); i++)
for j = 0 ; j < size(B) ; j++)
if Ai = Bi
print Ai
break

solution 2: sort the arrays first Note on sorting: * quicksort avergage complexity is O(Nxlog(N)), worst case is O(NxN) * heapsort is more interesting because it's worstcase complexity is also O(Nxlog(N))

minA, minB = 0
while (minA < sA and minB < sB)
if A[minA] < A[minB]
minA++
elif A[minA] > B[minB]
minB++
else
print A[minA]
minA++
minB++