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?

Solution 1:

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

Solution 2:

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²).

Solution 3:

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.