Asymptotic analysis of nest loop with condition (j=i+1)

user_11376348 0
Viewed 48

I am trying to understand the example for big O on this page: http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html

for (i = 0; i < N; i++) {
   for (j = i+1; j < N; j++) {
      sequence of statements }
}

I don't understand why inner loop will run for N if i=0. If i=0, then j=1, and as the result, number of iterations for inner loop should be N-1. I understand why the complexity of this loop is O(n^2). What I don't understand is why the inner loop starts with N number of iterations, not N-1.

big-o time-complexity
2 Answers

Your link has a slight error. Indeed the inner loop starts from N-1 iterations rather than N, but the result remains the same.

Starting from that first mistake they miss 1 on each iteration. They forgot the +1 the j=i+1 I guess.

user_68812400

The Big-O for this is O(n^2).

The outer loop is O(n) and the inner one is O(n - 1).

So the effective time complexity is O(n^(n - 1)) = O(n^2 - n).

Now for a larger value of n, the value of n^2 will be significantly higher than that of n and the net result will be dependent on n^2

Hence the time complexity will be O(n^2)

user_14752280
Related