CODEWITHSUNDEEP
time-complexity
screwnut
screwnut

Reputation: 1383

Is a nested for loop automatically O(n^2)?

I was recently asked an interview question about testing the validity of a Sudoku board. A basic answer involves for loops. Essentially:

for(int x = 0; x != 9; ++x)    
    for(int y = 0; y != 9; ++y)
        // ...

Do this nested for loops to check the rows. Do it again to check the columns. Do one more for the sub-squares but that one is more funky because we're dividing the suoku board into sub-boards so we end end up more than two nested loops, maybe three or four.

I was later asked the complexity of this code. Frankly, as far as I'm concerned, all the cells of the board are visited exactly three times so O(3n). To me, the fact that we have nested loops doesn't mean this code is automatically O(n^2) or even O(n^highest-nesting-level-of-loops). But I have suspicion that that's the answer the interviewer expected...

Posed another way, what is the complexity of these two pieces of code:

for(int i = 0; i != n; ++i)
    // ...

and:

for(int i = 0; i != sqrt(n); ++i)
    for(int j = 0; j != sqrt(n); ++j)
        // ...

Upvotes: 1

Views: 1516

Answers (2)

yuvgin
yuvgin

Reputation: 1362

Your general intuition is correct. Let's clarify a bit about Big-O notation:

Big-O gives you an upper bound for the worst-case (time) complexity for your algorithm, in relation to n - the size of your input. In essence, it is a measurement of how the amount of work changes in relation to the size of the input.

When you say something like

all the cells of the board are visited exactly three times so O(3n).

you are implying that n (the size of your input) is the the number of cells in the board and therefore visiting all cells three times would indeed be an O(3n) (which is O(n)) operation. If this is the case you would be correct.
However usually when referring to Sudoku problems (or problems involving a grid in general), n is taken to be the number of cells in each row/column (an n x n board). In this case, the runtime complexity would be O(3n²) (which is indeed equal to O(n²)).
In the future, it is perfectly valid to ask your interviewer what n is.

As for the question in the title (Is a nested for loop automatically O(n^2)?) the short answer is no.
Consider this example:

for(int i = 0 ; i < n ; i++) {
    for(int j = 0 ; j < n ; j * 2) {
       ... // some constant time operation
    }
}

The outer loops makes n iterations while the inner loop makes log2(n) iterations - therefore the time complexity will be O(nlogn).

In your examples, in the first one you have a single for-loop making n iterations, therefore a complexity of (at least) O(n) (the operation is performed an order of n times).
In the second one you two nested for loops, each making sqrt(n) iterations, therefore a total runtime complexity of (at least) O(n) as well. The second function isn't automatically O(n^2) simply because it contains a nested loop. The amount of operations being made is still of the same order (n) therefore these two examples have the same complexity - since we assume n is the same for both examples.
This is the most crucial point to sail home. To compare between the performance of two algorithms, you must be using the same input to make the comparison. In your sudoku problem you could have defined n in a few different ways, and the way you did would directly affect the complexity calculation of the problem - even if the amount of work is all the same.


*NOTE - this is unrelated to your question, but in the future avoid using != in loop conditions. In your second example, if log(n) is not a whole number, the loop could run forever, depending on the language and how it is defined. It is therefore recommended to use < instead.

Upvotes: 1

Tomingsun
Tomingsun

Reputation: 310

It depends on how you define the so-called N.

If the size of the board is N-by-N, then yes, the complexity is O(N^2).

But if you say, the total number of grids is N (i.e., the board id sqrt(N)-by-sqrt(N)), then the complexity is O(N), or 3O(N) if you mind the constant.

Upvotes: 0

Related Questions