Time complexity of a divide and conquer algorithm that searches for a value in an n x m table, rows and columns are sorted

Question

I am confused about the time complexity of this algorithm because I am thinking it could be something like T(n) = 3T(n/2) ... but since the array has a size of nxm instead of nxn and I am using recurrence, I do not how to get the time complexity of that and the recurrence equation...

class SearchInMatrix
{

    public static void search(int[][] mat, int fromRow, int toRow, 
                            int fromCol, int toCol, int key)
    {
        // Find middle and compare with middle 
        int i = fromRow + (toRow-fromRow )/2;
        int j = fromCol + (toCol-fromCol )/2;
        if (mat[i][j] == key) // If key is present at middle
        System.out.println("Found "+ key + " at "+ i + 
                            " " + j);
        else
        {
            // right-up quarter of matrix is searched in all cases.
            // Provided it is different from current call
            if (i!=toRow || j!=fromCol)
            search(mat,fromRow,i,j,toCol,key);

            // Special case for iteration with 1*2 matrix
            // mat[i][j] and mat[i][j+1] are only two elements.
            // So just check second element
            if (fromRow == toRow && fromCol + 1 == toCol)
            if (mat[fromRow][toCol] == key)
                System.out.println("Found "+ key+ " at "+ 
                                fromRow + " " + toCol);

            // If middle key is lesser then search lower horizontal 
            // matrix and right hand side matrix
            if (mat[i][j] < key)
            {
                // search lower horizontal if such matrix exists
                if (i+1<=toRow)
                search(mat, i+1, toRow, fromCol, toCol, key);
            }

            // If middle key is greater then search left vertical 
            // matrix and right hand side matrix
            else
            {
                // search left vertical if such matrix exists
                if (j-1>=fromCol)
                search(mat, fromRow, toRow, fromCol, j-1, key);
            }
        }
    }
}

I was thinking the recurrence equation could be T(n) = 3T(n/2) + O(1) but since the matrix size is n*m instead of n*n I dont know how to get the recurrence equation and therefore, the time complexity

Thanks