Trying to get my algorithm to O(n) runtime

Question

So in my advanced algorithms class, we are to write an algorithm for a program to find two numbers in two sorted arrays of integers. The format is A[i] + B[j] == x. The runtime of the algorithm needs to be O(n). I thought i had it and wanted to check so I emailed my professor and she told me my runtime was O(n^2). Here is my code:

int[] A = {1,2,3,4,5};
int[] B = {1,2,3,4,5,6};
int x = 4;
int i = 0;
int j = 0;

for(int n = 0; n < (A.length*B.length); n++) {

    if(i >= A.length)
        i = 0;

    if(n % B.length == 0)
        j++;

    if(A[i] + B[j] == x) {
        System.out.println(A[i] + " + " + B[j] + " = " + x);
        break;
    }
    i++;
}

EDIT

I do apologize if this is still incorrect. I never really grasped the concept of Big-Oh. Would this change the runtime to O(n)? I got rid of the A.length*B.length and tried something a little different.

int[] A = {1,2,3,4,5};
int[] B = {1,2,3,4,5};
int x = 5;
int i = 0;
int j = 0;

while(i < A.length) {

    if(B[j] == x - A[i]) {
        /* exit */ }

    if(j >= B.length) {
        j = 0;
        i++; }

    j++;
}

Answer 1

Solution 1:

Add all values in B to a Map with B value as the map key, and B-index as the map value.

Iterate A, and calculate desired B value as B = x - A. Look for it in the map, and if found, you then have the index.

You will only iterate A and B once each. Adding a single value to map is O(1), and looking up a value is O(1), assuming a HashMap, so overall is O(n).

---

Solution 2:

Iterate A ascending, and B descending.

For each value in A, look at current B value. Walk down B until A + B <= x (or you reach beginning of B).

You will only iterate A and B once each, so O(n).

Solution 2 requires less memory (no map), and is likely faster (no time spent building map).

---

UPDATE Here is code:

The above descriptions were based on need for index of values, and the code for each solution is:

Solution 1

private static void findSum(int[] a, int[] b, int x) {
    Map<Integer, Integer> bIdx = new HashMap<>();
    for (int j = 0; j < b.length; j++)
        bIdx.put(b[j], j);
    for (int i = 0; i < a.length; i++) {
        Integer j = bIdx.get(x - a[i]);
        if (j != null)
            System.out.println("a[" + i + "] + b[" + j + "] = " + a[i] + " + " + b[j] + " = " + x);
    }
}

Solution 2

private static void findSum(int[] a, int[] b, int x) {
    for (int i = 0, j = b.length - 1, sum; i < a.length && j >= 0; i++) {
        while (j >= 0 && (sum = a[i] + b[j]) >= x) {
            if (sum == x)
                System.out.println("a[" + i + "] + b[" + j + "] = " + a[i] + " + " + b[j] + " = " + x);
            j--;
        }
    }
}

Test

int[] a = {1,2,3,4,5};
int[] b = {1,2,3,4,5,6};
findSum(a, b, 4);

Output (same from both)

a[0] + b[2] = 1 + 3 = 4
a[1] + b[1] = 2 + 2 = 4
a[2] + b[0] = 3 + 1 = 4

Solution 1 using Set

If you don't need index position, then a Set is better for solution 1:

private static void findSum(int[] aArr, int[] bArr, int x) {
    Set<Integer> bSet = new HashSet<>();
    for (int b : bArr)
        bSet.add(b);
    for (int a : aArr)
        if (bSet.contains(x - a))
            System.out.println(a + " + " + (x - a) + " = " + x);
}

Output

1 + 3 = 4
2 + 2 = 4
3 + 1 = 4

Answer 2

Here is an example of how you can measure your time, i've included another method to find the numbers you mentioned. See the difference in runtime:

    int[] A = {1,2,3,4,5};
    int[] B = {1,2,3,4,5,6};
    int x = 4;
    int i = 0;
    int j = 0;

    long t1 = System.nanoTime();

    for(int n = 0; n < (A.length*B.length); n++) {

        if(i >= A.length)
            i = 0;

        if(n % B.length == 0)
            j++;

        if(A[i] + B[j] == x) {
            System.out.println(A[i] + " + " + B[j] + " = " + x);
            break;
        }
        i++;
    }
    long t2 = System.nanoTime();
    System.out.println("Time 1: "+(t2-t1));

    //Here's the other method
    long t3 = System.nanoTime();
    for (int n = 0;n<B.length;n++){
        for (int m =0;m<A.length;m++){
            if(A[m]+B[n]==x){
                System.out.println(A[m] +" + "+B[n] +" = "+ x);
            }
        }
    }
    long t4 = System.nanoTime();
    System.out.println("Time 2: "+(t4-t3));

Answer 3

Here is the code, for Andreas's Solution 1, that I came up with:

int[] A = {2,3,4};
int[] B = {7,9};
Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
int x = 10;
int b;

for(int i = 0; i < B.length; i++) {
    hashMap.put(B[i], i);
}

for (int n = 0; n < A.length; n++){
    b = x - A[n];
    if(hashMap.get(b) != null)
        System.out.println(A[n] + " + " + b + " = " + x);
}