You are given two sequences of numbers A and B and another number m. You have to tell whether there exists **a** and **b** such that **a+b = m.**

A naive algorithm would be to loop over the elements of **A** and for each element loop over the elements of **B** to see whether we can find a match or not.

foreach(A[i])

foreach(B[i])

if (A[i] + B[i] = m) return 0;

return 1;

This is **O(n^2)** in complexity. An improvement could be to sort the arrays and do a binary search on **B** for each element in **A.** This would take **O(nlogn)** for sorting both arrays and **O(nlogn)** for doing a binary search on** B.**

Another improvement could be to sort the __larger of the arrays__ and doing a binary search on that sorted array. The complexity is still the same, but we save time by not sorting one of the arrays.

### Like this:

Like Loading...

*Related*