Assume a 2D [n][n] matrix of 1's and 0's. All the 1's in any row should come before 0's. The number of 1's in any row i should be at least the number of 1's row i 1. Find a method and write a Java program with O(n) complexity to count the 1'sin the array.

For example we have the following array:

{{1,1,1,1},
 {1,1,1,1},
 {1,1,0,0},
 {1,0,0,0}}

I have written a code that counts the 1's correctly but I am not sure if the complexity is O(n) or O(n^2).

The code is the following:

public class SpecialMatrix {

    public static void main(String[] args) {
        int[][] a = {{1,1,1,1},
                     {1,1,1,1},
                     {1,1,0,0},
                     {1,0,0,0}};
        
        int n = 4;
        int cnt=0;
        int row; 
        int col = 0;
        for (row = n-1; row>=0; row--)
        {
            while(col<n && a[row][col]==1)
            {
                cnt = cnt   (row   1);
                System.out.print("Row: "   row   " Col: "   col   " Cnt: "   cnt);
                System.out.println();
                col  ;
            }
            System.out.println();
        }
        System.out.print(cnt);
        
    }
        
}

The output looks like this:

Row: 3 Col: 0 Cnt: 4

Row: 2 Col: 1 Cnt: 7

Row: 1 Col: 2 Cnt: 9
Row: 1 Col: 3 Cnt: 11


11

I would like some help regarding the complexity of the code. Is it O(n) or O(n^2)?

Thanks!

CodePudding user response：

Your outer loop must always execute n times. You can't alter that. So as you compute the count by taking advantage of the relationship between rows, the inner while loop is governed by the col and if the current row/col has a 1. Based on the result of the col to row comparison, the inner loop may execute anywhere from 0 to n times and no more. So it is running at O(n)

The number of times, the inner loop is entered, and for which iteration of the outer loop, is dependent on the particular groupings of the 1's and 0's