What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?

Yep, it's still O(n^2), it has a smaller constant factor, but that doesn't affect O notation.

Yes. Recall the definition of Big-O: O(f(n)) by definition says that the run time T(n) ≤ kf(n) for some constant k. In this case, the number of steps will be (n-1)+(n-2)+...+0, which rearranges to the sum of 0 to n-1; this is

T(n)=(n-1)((n-1)+1)/2.

Rearrange that and you can see that T(n) will always be ≤ 1/2(n²); by the definition, thus T(n) = O(n²).

It's N squared if you ignore the System.out.println. If you assume that the time taken by that will be linear in its output (which it may well not be, of course), I suspect you end up with O ( (N^2) * log N).

I mention this not to be picky, but just to point out that you don't just need to take the obvious loops into account when working out complexity - you need to look at the complexity of what you call as well.

Let us trace the number of times each loop executes in each iteration.

for (int i = 0; i < N; i++) {  // outer loop
    for (int j = i + 1; j < N; j++) {  // inner loop
        System.out.println("i = " + i + " j = " + j);
    }
}

In the first iteration of the outer loop (i = 0), the inner loop executes N - 1 times.

In the second iteration of the outer loop (i = 1), the inner loop executes N - 2 times.

In the third iteration of the outer loop (i = 2), the inner loop executes N - 3 times.

. . .

In the N - 2th iteration of the outer loop (i = N - 3), the inner loop executes 2 times.

In the N - 1th iteration of the outer loop (i = N - 2), the inner loop executes 1 time.

In the last (Nth) iteration of the outer loop (i = N - 1), the inner loop executes 0 times.

Therefore, the total number of times this code executes is

N - 1 + N - 2 + N - 3 + … + 2 + 1 + 0

= 0 + 1 + 2 + … + N - 3 + N - 2 + N - 1

Substituting this in the Sum of Natural numbers Formula,

= (N - 1)((N - 1) + 1) / 2

= (N - 1)(N) / 2

= ((N^2) - N) / 2

= O(N^2), assuming System.out.println executes in constant time O(1).

——————

Also, do take a look at these

1. https://stackoverflow.com/a/71805214/17112163
2. https://stackoverflow.com/a/71146522/17112163
3. https://stackoverflow.com/a/69821878/17112163
4. https://stackoverflow.com/a/72046825/17112163
5. https://stackoverflow.com/a/72046933/17112163

Yes, it would be N squared. The actual number of steps would the sum of 1 to N, which is .5*(N - 1)^2, if I'm not mistaken. Big O only takes into account the highest exponant and no constants, and thus, this is still N squared.

For the given program:

for (int i = 0; i < n; i++)
    for (int j = i; j < n; j++)
        println(...);

Consider n = 3:

i will have the values 0, 1 and 2.

For i = 0: println will execute 3 times
for i = 1: println will execute 2 times
for i = 2: println will execute 1 times

Thus the println function will execute 3 + 2 + 1 times, i.e. n(n+1)/2 times.

Hence O(n(n+1)/2) = O(n^2).