Why is the runtime for this O(n)?

Question

so in class we went over this bit of Java, and we were told to find the runtime.

for(int i=0; i<N; i=i+2){
            for(int j=N; j<N; j++){
                for(int k=0; k<N; k++){
                    System.out.println(i*j);
                    System.out.println(i);
                }
            }
        }

        for(int k=0; k<100; k++){
            System.out.println(k);
        }

Apparently the runtime for this is O(n) but I don't know why. Wouldn't this be O(n³) because of the for loops? Are there any tips or tricks to being able to tell immediately what the runtime is that I am missing?

Answer 1

For the given code, you should have the following time complexity:

T(n) = 1 + N/2 (1 + 2) + 1 + 1 + 1 + 100 (1 + 2) ≈ N/2

This means that your overall complexity is O(n). Because the second for loop (the first nested for loop) never executes, due to its condition, you don't have O(n^3) complexity. If the second for loop was written as for(int j=0; j< N; j++), then you would have O(n^3) complexity.