0

I have the quadratic solution for the problem as below:

A = [12, 45, 23, 50, 87, 57]
B = [32, 10, 12, 57, 34, 99]

for i in range(len(A)):
    for j in range(len(B)):
         if A[i] == B[j]:
               print(A[i])

This is of course O(N^2).

Another solution I thought about is sorting list B which is O(n*log(n)) then binary search into Bis O(log(n)), and then doing that N times for all items in A. So that's a worst case complexity of O(2*n*log(n))) but w can drop the 2 since it's a constant and we have O(n*log(n)).

Is that correct? Is there a way to improve that even further?

Sam Hammamy
  • 10,819
  • 10
  • 56
  • 94
  • Set intersections are O(N). – Martijn Pieters May 06 '17 at 14:47
  • @MartijnPieters I am less interested in the python way of doing it; i.e. just creating a `set` using builtins and doing a union. I am more interested in the explanation of that algorithm. – Sam Hammamy May 06 '17 at 14:55
  • 1
    `set` uses a hash table, so membership tests are O(1). Creating an intersection is then just a question of looping over one set (O(N)) and testing each value against the other set (O(N) times O(1)). – Martijn Pieters May 06 '17 at 15:34

0 Answers0