How can I find the time complexity?

Question

The main is to get a 6*6grid from user. The input will be stored in a 2d array. Is the time complexity should be O(n^2)? Since, I have a nested loop. But the code operates in a fixed 6 rows and 6 cols that are static. Or the time complexity should be O(n)? as the number of row and column are constant and set equals to 6.

public class MatrixGrid {
    private static char[][] grid = new char[6][6];
    private static int rows = 6;
    private static int cols = 6;

    public static void main(String[] args) {
        MatrixGrid matrixGrid = new MatrixGrid ();
        matrixGrid.getGridFromUser();  //get user input
        int totalHomeAreas = 0;
        int maxHomeAreaSize = 0;

        for (int i = 0; i < rows; i++) {  //---n
            for (int j = 0; j < cols; j++) {  //--n
                if (grid[i][j] == 'H') {
                    int currentSize = matrixGrid.dfs(i, j);
                    totalAreas++;
                    maxAreaSize= Math.max(maxAreaSize, currentSize );
                }
            }
        }
}

What's the correct time complexity?

Answer 1

The time complexity in all cases is based on your line int currentSize = matrixGrid.dfs(i, j);. Since there is not metion on it, we assume the time complexity of matrixGrid.dfs(i, j) is O(1).

Then the time complexity of main is O(n) when we assign n = size(grid) = rows * cols, or O(n^2) when we assign n = rows = cols; both options are correct.

Finally, considering the constant time complexity, you should define your data constraints. If you define the constraints as rows = 6, cols = 6, then there is constant time complexity O(1). Otherwise, if the constraints are more like rows = n, cols = n, 0 <= n <= 10^4, then the time complexity is O(n^2), similar to the examples mentioned above.

So, the key to calculating time complexity is "the constraints of the data".