Searching/Sorting Algorithm

Question

I just started studying algorithms and data structures and came across this problem:

Given $x \in \mathbb{N}$ and two integer Arrays $A_1$ and $A_2$ each of the length $n$. Write an algorithm in pseudocode that has a time complexity of $O(n.log(n))$ or better to determine the set $$X = \{ (a,b) | a \in A_1 \land b \in A_2 \land a + b = x \}$$

My idea was to first sort the two arrays, loop through the first array and then perform a binary search through the second one and then, if such a couple (a,b) exists, add the result to a 2D Array(?). But i'm not sure if the time complexity is $O(n.log(n))$ or better.

Thanks in advance!

Answer 1

We can do this in linear time. In one pass, we can place the elements of $A_2$ in a hash set which has constant time access. Call the hash set $H$.

Then we get

for num in A_1
   if H.contains(x-num) then add (num, x-num) to X

This makes a one time pass through $A_1$ and for each value executes a constant time access.

Therefore, this algorithm is $O(n)$

Answer 2

Your approach is $O(n \log n)$ assuming you use a sort of that order. Given that the sort is that order, you then are going through $n$ elements of the first array and doing a binary search, which is of order $\log n$, for each one. Each step is of order $n \log n$ so the whole thing is.