Two Sorted Arrays, sum of 2 elements equal a certain number
<p>I was wondering if I could get some help. I want to find an algorithm that is THETA(n) or linear time for determining whether 2 numbers in a 2 sorted arrays add up to a certain number.</p>

<p>For instance, let's say we have 2 sorted arrays: X and Y</p>

<p>I want to determine if there's an element of X and an element of Y that add up to exactly a certain number, let's say 50.</p>

<p>I have been able to come up with these algorithms in Python so far, but I am pretty sure they are order of THETA(n^2) rather than THETA(n).</p>

<pre><code>def arrayTestOne(X,Y):
    S =[1 for x in X for y in Y if x+y == 50]

def arrayTestTwo(X,Y):
    for x in X:
        for y in Y:
            if x + y == 50:
                print("1")
</code></pre>

<p>I'm thinking it's the double for loops that break the linear time, but how else would you iterate through 2 lists? Any thoughts would be appreciated.</p>

<p>What you can do is start with the highest in one list and the lowest in the other, and check the sum. </p>

<p>If the sum is your target, you're done. </p>

<p>If it's too high, go to the next highest value in the first list.</p>

<p>If it's too low, go to the next lowest value in the second. </p>

<p>If you go through both lists without reaching the target, you return false.</p>

python arrays algorithm big-o