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 ?