Big O Notation- Finding the Complexity

I'm working on a quiz- I got all right but the following snippet. Help me understand which notation this would be?

My selections are: O(n^2), O(n^3), O(nlogn), and O(n+n^2)

Snippet is:

   for (int i = 0; i < n; i++) { 
     System.out.println("hello");
   } 
   for (int i = 0; i < n; i++) { 
     for (int j = 0; j < i; j++) { // NOTE j < i here. 
       System.out.println("hello");
     }
  } 

The first loop is easy: the body runs exactly n times, so it's O(n).

The second one requires a bit more thinking. It's clear that the outer loop runs n times, but how often is the inner loop body executed? The first time through the outer loop, we have i == 0, so the inner loop body is executed 0 times (j < i is false even for j == 0). The second time, i == 1 so the inner loop body is executed 1 times. In general, it's executed i times, for i = 0, ..., n-1.

So the total number of executions of the inner loop body is, let's call it S, is S = 0 + 1 + ... + n-1. Now there's a nice trick to make that into a closed form equation. Write it down once, and then once more in reverse:

 S =  0  +  1  + ... + n-2 + n-1
 S = n-1 + n-2 + ... +  1  +  0

Then add the two equations together:

 S  =  0  +  1  + ... + n-2 + n-1
 S  = n-1 + n-2 + ... +  1  +  0
------------------------------- +
2*S = n-1 + n-1 + ... + n-1 + n-1

So 2*S is equal to n times n-1. From this, we easily find S = n * (n-1) / 2. This can be rewritten as S = ½*n^2 - ½*n. In the big-O form, only the highest order term survives, and the constant ½ does not matter, so this is O(n^2).

A more "handwavy" way to get the same result is: the inner loop runs, on average, n/2 times (give or take one), and the outer loop runs n times, again giving O(½*n*n) = O(n^2).

Combined with the O(n) of the first loop, which becomes asymptotically irrelevant compared to the O(n^2), the expected answer is probably O(n^2).

But note that technically O(n+n^2) is also correct because O(n + n^2) = O(n^2). Again, the lower order term n does not matter asymptotically. Even O(n^3) is technically correct because n^3 dominates n^2; however, the complexity is neither Ω(n^3) nor θ(n^3).

(This is what I think, I can't comment because I don't have enough reputation but I wanted to throw this out)

The first loop is linear and thus has the complexity of just O(N).

However, for the second/third loop, the second loop is a loop that loops N times. The inner loop will run N/2 time because j is always going to be less than i, (and never equal). Thus, the complexity for these loops is N(N/2), or N^2/2. Because Big O is a constant, N/2 and N - 1 are the same time, so we can also say that it is N(N-1), or N^2 - N.

If we add both complexities together, we have (N) + (N^2 - N), we get N^2. Thus the final result is O(N^2).