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.
For instance, let's say we have 2 sorted arrays: X and Y
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.
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).
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")
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.