I am supposed to design an O(n) algorithm that solves the following problem.
Input: An integer v and 2 sorted arrays A and B, each having n integers.
Output: Yes if and only if there exist i and j such that v = A[i] + B[j].
No if no such i and j exist.
The algorithms I came up with were linear search, which gave O(n^2) and binary search, which gave O(n log n). None gave me an O(n) algorithm.