a+b = m

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s