How do I not understand Big-O of these Java functions?

Question

In the first example, it turned out: O (n), I don’t know why.

Example 1:

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 still O(n)
     // Overall I think it O(n)

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

Example 2:

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 O(n^2)

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

Example 3:

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 O(n^2)

The last 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 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 O(n^2)

Can someone please read them and explain what I'm doing wrong. My reasoning is that we are tracking the variable "n", because this is what the user entered, and we see how it grows. If it is one operator, then the constant time is O (1), if it is in a loop, which is O (n) by default, if it is in a nested loop, that is O (n ^ 2).

Please help thank you

Answer 1

1, 2 4 , , 3.

for (i = n - 3; i <= n - 1; i++), , n-3 n-1 (), 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)

Answer 2

-, .

, 1, n. Big O , . , 2n n, O(n).

, , n, , n, , . , , n, n^2. Big O - , O(n^2).

, 3, . n, , 4 ( ). for 1, O(n).

, O(n) ( , O(n/3) O(n)). for - . O(n*2) O(n). O(n^2).

Answer 3

.

:

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 still O(n)
     // Overall I think it O(n)

:
O (n), , n , n . O(n + n) => O(2n). , "" (< = , ).

:

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 O(n^2)

:
, n , , n . , O(n*n) => O(n^2). .

:

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 O(n^2)

:
n - 3 n - 1, n. , O(n)

:

for (a = 1; a <= n / 3; a++) // will be O(n/3) thus O(n)
     for (b = 1; b <= 2 * n; b++) // since it 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 O(n^2)

Explanation:
The difference between this and the above code is that this outer loop cycle depends on the value n. As it grows, it nincreases n/3(unlike n - 3and n - 1, which makes it O(n^2).