Problem name

[AEmme]

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.

[BioPhysEngr]

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?

[elrabin]

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.

[BioPhysEngr]

Not sure I see the time complexity you state. Assume without loss of generality that len(A) >= len(B), then the algorithm is:

foreach b in B
    if k-b in A
        return a, b
endfor

otherwise return false

Where if k-b 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?