# Searching/Sorting Algorithm

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.

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)$$

• Well this is a lot more efficient, thank you! Commented Nov 15, 2020 at 11:53

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.