What is the Big-O time complexity of the following nested loops:
for(int i = 0; i < N; i ++)
{
for(int j = i + 1; j < N; j++)
{
System.out.println("i = " + i + " j = " + j);
}
}
Would it be O(n^2) still?
views:
2255answers:
5
+9
A:
Yep, it's still O(n^2), it has a smaller constant factor, but that doens't affect O notation.
Alex Gaynor
2008-12-12 06:47:20
+3
A:
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.
Charles Graham
2008-12-12 06:49:17
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).
2009-01-25 04:53:18
+5
A:
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.
Jon Skeet
2008-12-12 07:22:21
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.
2008-12-12 08:04:10
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
2008-12-12 08:38:20