Given an two sorted arrays X and Y, both of size n. Determine if there is an element x of X and an element y of Y such that x = 3y. The algorithm needs to run in linear time in the worst case. At the moment, the algorithm runs in O(n^2). I am unsure how to leverage the fact that the algorithm is sorted to have a scenario where the worst case would have O(n). I am aware of the fact that a binary search has O(log n). public static void main (String [] args){    int[] listX = {1,2,3,4};    int[] listY = {1,2,3,8};    for(int x = 0; x<listX.length; x++)        for(int y = 0; y<listY.length; y++)        {            if(listX[X] == (3*listY[y]))            {                System.out.println(TRUE);                break;            }        }}
How to get an O(n) for a search algorithm
algorithms;search algorithms