How am I misunderstanding Big-O of these Java functions?

Question

For the first example, this turned out to be: O(n), not sure why though.

Example1:

for (k = 0; k <= n / 8; k++) // will be O(n/8) thus, O(n)
     System.out.println(k); // will be O(n)
System.out.println("Hello World!"); // will be O(1) because not in a loop
for (p = n; p >= 1; p--) // will be O(n-1) thus, O(n) 
     System.out.print(p % 2); // not sure what % will do here, but I think it's still O(n)
     // Overall I think it's O(n)

For the second example. this turned out to be O(n^2), not sure why.

Example2:

for (k = 0; k < n - 1; k++) // will be O(n-1) or O(n)
     for (m = k + 1; m < n; m++) // will be O(n^2) because nested loop
        System.out.println(k * m); // not sure what this will do but I think it will be O(n^2)
     // Overall I think it's O(n^2)
 
 

For the third example, this turned out to be O(n), but not sure why.

Example3:

for (i = n - 3; i <= n - 1; i++) { // not sure here, maybe O(n-1), thus O(n)
     System.out.println(i); // since it is nested then O(n)
     for (k = 1; k <= n; k++) // since this is the second loop, then O(n^2)
        System.out.println(i + k); // not sure what this will do, but I think it will be O(n^2)
} // Overall I think it's O(n^2)
 

 

The final example turned out to be O(n^2), also not sure why.

Example4:

for (a = 1; a <= n / 3; a++) // will be O(n/3) thus O(n)
     for (b = 1; b <= 2 * n; b++) // since it's a nested loop it will be O(2n^2) thus O(n^2)
        System.out.println(a * b); // not sure what this will do, but I think it will be O(n^2)
     // Overall I think it's O(n^2)

Could someone please read through these and explain what I am doing wrong. My reasoning is that we track the 'n' variable because that's what the user has inputted and we see how that grows. If it's a single statement, that's constant time O(1), if it's in a loop that's by default O(n), if it's in a nested loop that's O(n^2).

Answer 1

Since your guess in examples 1, 2 and 4 is equal to your solution, I'm assuming you only have trouble with example 3.

When you look closely at the first line for (i = n - 3; i <= n - 1; i++), you will see that it goes from n-3 to n-1 (inclusive), thus it does not depend on the value of n.

for (i = n - 3; i <= n - 1; i++) { // O(3), so O(1) (since it'a a constant factor)
    System.out.println(i); // nested, O(1)
    for (k = 1; k <= n; k++) // O(n)
        System.out.println(i + k); // nested, so O(n)
} // Overall O(n)