Find the sum of two numbers that are from two different arrays.

[bMorgan]

The sum is a specific number. Is there any way to solve this problem in linear-time algorithm?

[Zachm]

Do you want to find two numbers X, Y, where X is a number from the first array and Y is a number from the second, such that X + Y = S, and S is some predefined value ?

Are the arrays sorted ?

Regards,
Zachm

[bMorgan]

I need to add that there are n integers in each array, and each integer is between 0 and n^5.

[bMorgan]

Do you want to find two numbers X, Y, where X is a number from the first array and Y is a number from the second, such that X + Y = S, and S is some predefined value ?

Are the arrays sorted ?

Regards,
Zachm

Yes.

[bMorgan]

but the arrays are not sorted

[BioPhysEngr]

If they're sorted, the algorithm should be obvious.

If they're not sorted, you can't sort (and use the obvious algorithm then) them because that will cost O(n log n) which is supralinear, so you'll need to do something tricky...

This looks like a homework question so I will refrain from just posting the answer. Basically the problem is that you need an efficient way to check if the difference S-X[i] is in array Y. I implemented a way of doing this just to measure the time it takes to solve 1000 of these and got these results:


n Time in seconds
10 0.01
20 0.005
40 0.01
80 0.016
160 0.039
320 0.067
640 0.117
1280 0.306
2560 0.768
5120 1.064
10240 2.369
20480 5.167
40960 14.517


This looks pretty linear to me, although the pattern of residuals hints that it might actually be exponential. I suspect this might be due to the time spent allocating one of the data structures. Not sure...

When I modified the search routine to use a constant-size data structure (and so avoid differences in their allocation speed), I lost any clear dependence on size, so... dunno. Those benchmarks don't seem very informative.

So short answer: yes, I think you can, but I'm not really sure.

I should note that I modified the problem to facilitate computation. Values range between 0 and n^2 instead of n^5. I don't see how this affects algorithmic time complexity, however.

[BioPhysEngr]

Eh, maybe the n^5 thing does matter. My find match subroutine returns as soon as any match is found. The probability of finding a match is probably dependent on the size of the array (and the numbers that can be contained within)...

[nuzzle]

---

[superbonzo]

I suppose you are seeking an avarage-case algorithm complexity, so...

drop all the array elements greater then your input number and answer the following question : what's the avarage size of the resulting reduced arrays with respect to n ? ;)