Trouble finding understanding why complexity of two nested loops is O(n)?

Question

So in the following code, j executes n times when i = 0. As soon as i iterates once (i = 0,2,3....n), j never executes, as the condition of the if statement is true and n is added to j. i continues to iterate until n which is when the loop (both loops) stop execution and the method ends.

public static void main(String[] args) {
        int x = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(j < i) j = j + n;
                else x = x+1;
            }
        }
    }

My confusion lies in why the time complexity is O(n) when both loops iterate to n at some point, i always iterates to n and j iterates to n when i = 0... Should it not be O(n^2) as we are multiplying nxn?

Answer 1

The innermost condition, if (j < i), is always true when i >= 1, as j is initialized to 0. Because you increment j by n inside the if-statement, this is equivalent to calling break;, thus exiting the innermost for-loop after a single iteration.

So to answer your question, the time complexity is O(n) because the innermost for-loop will only iterate 2n - 1 times:

• It iterates to n when i == 0.
• When i > 0, it only iterates once.

Thanks for Phoenix1355 for pointing this out below in the comments.

Answer 2

You can also analyze the time complexity by passing different inputs (n). I copied the same code and created a separate function:

private static void testComplexity(int n) {
    int x = 0;
    int N1 = 0, N2 = 0;
    for (int i = 0; i < n; i++) {
            N1++;
        for (int j = 0; j < n; j++) {
                N2++;
            if(j < i) j = j + n;
            else x = x+1;
        }
    }
    System.out.println("input is : " + n + " and N1 " + N1 + " and N2 : " + N2);
}

public static void main(String[] args) {
    int[] inputs = new int[]{10, 100, 1000, 10000};
    for(int input : inputs) testComplexity(input);
}

The output is:

input is : 10 and N1 : 10 and N2 : 19
input is : 100 and N1 : 100 and N2 : 199
input is : 1000 and N1 : 1000 and N2 : 1999
input is : 10000 and N1 : 10000 and N2 : 19999

I created another function for QUADRATIC

    private static void testComplexity2(int n) {
    int N1 = 0, N2 = 0;
    for (int i = 0; i < n; i++) {
            N1++;
        for (int j = 0; j < n; j++) {
                N2++;
        }
    }
    System.out.println("input is : " + n + " and N1 " + N1 + " and N2 : " + N2);
}

The output is :

input is : 10 and N1 10 and N2 : 100
input is : 100 and N1 100 and N2 : 10000
input is : 1000 and N1 1000 and N2 : 1000000
input is : 10000 and N1 10000 and N2 : 100000000

Do you see difference ?