Big-oh time complexity for nested for loop

Question

Hi, I have a question here the loop is:

for (i=0; i < n; ++i)
   for (j = 3; j < n; ++j)
           {
            ...
           }

I kind of understand how to calculate the big-oh but I am not entirely sure on how to do it. The outer loop executes n times and the inner loop executes i times for each value of i. The complexity is supposed to be N^2 (I think). Can you guys elaborate on how this is calculated? I understand some of it but not all of it.

Answer 1

It is (n*(n-3)) = n²-3n and for very big n it is close to n². So for Big-Oh notation I would write O(n²) because the -3n can be ignored.

---

Just a correction to your test in the question: the outer loop executes n times, the inner (n-3) times for each iteration on the outer loop.

Answer 2

The complexity isn't necessarily O(n^2). It actually depends on what is going on in the "...". If the stuff in the inner loop has O(1) complexity, then yes, the overall complexity is O(n^2). The reason is because on any iteration of the outer loop you have n-3 iterations of the inner loop. Each iteration of the inner loop has 1 execution of the body, which we assume is O(1). So, you end up with n*(n-3) executions of the body. If we assume the body is O(1), then the complexity of the whole thing is O(n*(n-3)) = O(n^2).

Answer 3

Hi, thanks for the replies, I can see now that the inner loop executes n-3 times due to j starting out as 3. The outer loop executes n times as usual. As for the people who were confused that I wrote the problem wrong, that is how the problem is given. I triple checked and its exactly how I wrote it. Thanks a lot for the help!

Answer 4

In general, the construct of nested for loops is O(n^2), but there are some exceptions. In computer graphics, it is normal to see something like:

for (int x=0; x < width; x++) {
  for (int y=0; y < height; y++) {
    // Do something on a specific pixel in the image in constant time
  }
}

And see it called O(n) instead on O(n^2) because n is assumed to be the number of pixels in some contexts, instead of the linear size of the image. So, the "n^2" is already taken into account. There are probably other domain-specific contexts where the accepted definition of "n" may not be immediately obvious just from looking at the code.