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 doens't affect O notation.

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.

You say it implicitly, but it should be noted explicitly that complexity depends on what you consider "unit of work". If println is unit of work, then it's O(n^2), if machine instruction is unit of work, then it's as you say. – J S Dec 12 '08 at 8:04 It's pretty odd for the unit of work to depend on n though - or at least, it makes it less useful in the real world, IMO.

– Jon Skeet Dec 12 '08 at 8:38.

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.

You're off by just a bit - the sum from 1 to n is n*(n+1)/2, or .5*n^2+.5*n, which is clearly O(n^2). – user57368 Jan 25 '09 at 4:53.

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

Yup,,,,,in worst case analysis its surely N square.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.