Run time of nested loops

Question

Sorry if this question has already been asked, I wasn't sure how to search for it.

Say you have the following loop

    for (i=0; i < n; i++)
         for(j = i; j < n; j++)

Would this be O(n^2) or O(nlog(n)) and why?

Answer 1

The outer loop's runtime (by itself) is O(n), and the inner loop's runtime is O(n-i). So the loop's time would be (n)(n-i), and when you throw away the constant i, the runtime would be O(n^2).