
August 28th, 2011, 01:28 PM
#1
Problem name
Hi, this is odd, i'm solving a problem but i don't know its name.
The problem is the following:
There are 2 (ordered) numbers array V and W.
We have to find a number k which is the result of V[i]+W[j].
There is a literature algorithm which solves it:
i=0;
j=size(W);
while(true)
If (V(i)+W(j)==k)
return i,j;
else if V(i)+W(j)>k
j;
else if V(i)+W(j)<k
i++
Do you remember the name of the problem or the name of the algorithm?
Thank you.

August 29th, 2011, 06:24 PM
#2
Re: Problem name
Seems kind of simple to be a named problem... Is there a reason you think it has a formal name?
The 'literature' algorithm you cited is very simple. What is the source? Do they quote a name?
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.

August 30th, 2011, 03:44 PM
#3
Re: Problem name
This problem is called, "given two sorted arrays A and B and an integer k, find the element in A and the element in B that sum to k".
Only interesting problems get names. This one is not interesting.
Also, the solution you gave is not the most efficient. If len(A) >= len(B), It is O(len(A)). If you do a binary search across A and B, you can reach the solution in O(log(len(A))) time.

August 30th, 2011, 11:43 PM
#4
Re: Problem name
Not sure I see the time complexity you state. Assume without loss of generality that len(A) >= len(B), then the algorithm is:
Code:
foreach b in B
if kb in A
return a, b
endfor
otherwise return false
Where if kb in A can be done in O(log(A)) time by binary search. This gives a runtime complexity of O(B log(A)).
By contrast, the algorithm given by AEmme has complexity O(A+B) ~ O(A), which is likely less.
Agree? Or did I miss something?
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.
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
OnDemand Webinars (sponsored)
