
February 6th, 2011, 11:32 PM
#1
Find the sum of two numbers that are from two different arrays.
The sum is a specific number. Is there any way to solve this problem in lineartime algorithm?

February 7th, 2011, 12:43 AM
#2
Re: Find the sum of two numbers that are from two different arrays.
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

February 7th, 2011, 12:47 AM
#3
Re: Find the sum of two numbers that are from two different arrays.
I need to add that there are n integers in each array, and each integer is between 0 and n^5.

February 7th, 2011, 12:47 AM
#4
Re: Find the sum of two numbers that are from two different arrays.
Originally Posted by 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
Yes.

February 7th, 2011, 01:01 AM
#5
Re: Find the sum of two numbers that are from two different arrays.
but the arrays are not sorted

February 7th, 2011, 02:49 AM
#6
Re: Find the sum of two numbers that are from two different arrays.
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 SX[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:
Code:
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 constantsize 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.
Last edited by BioPhysEngr; February 7th, 2011 at 02:50 AM.
Reason: increase clarity
Best Regards,
BioPhysEngr
http://blog.biophysengr.net

All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

February 7th, 2011, 03:07 AM
#7
Re: Find the sum of two numbers that are from two different arrays.
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)...
Best Regards,
BioPhysEngr
http://blog.biophysengr.net

All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

February 7th, 2011, 09:20 AM
#8
Re: Find the sum of two numbers that are from two different arrays.

February 7th, 2011, 11:02 AM
#9
Re: Find the sum of two numbers that are from two different arrays.
I suppose you are seeking an avaragecase 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 ?
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
