Time complexity of recursive code in 2D matrix (find the largest square containing only 1's)

Viewed 37

I'm having an m x n binary matrix filled with 0's and 1's, and I'm finding the largest square containing only 1's.

I have written the recursive code for it(max stores the size of largest square containing only 1's) and it works fine but i want to know the time complexity of this code

int max = 0;    
int solveRec(char[][] mat, int i, int j){
    if(i>=mat.length || j>=mat[0].length)
        return 0;
    
    int right = solveRec(mat, i, j+1);
    int diagnol = solveRec(mat, i+1, j+1);
    int down = solveRec(mat, i+1, j);
    
    if(mat[i][j]=='1'){
        int ans = 1+Math.min(right, Math.min(diagnol, down));
        max = Math.max(max, ans);
        return ans;
    } else
        return 0;
}

I know to find the Time complexity of 1D array recursive calls where array size decreases but here there are 3 recursive calls

0 Answers
Related