sorted matrix search master theorem analysis

Question

So the problem is to find whether x is in one of the elements of a sorted matrix ascending by row and by column.

example :

1 2 3

4 5 6

7 8 9

I'm interested to find the time complexity of the divide and conquer solution of this problem. I've googled it but i've found only for the O(m+n) solution, and also from this Search a sorted 2D matrix. but he says(comment on answer) that "T(R) = 3T(R/4)", why is the f(R) = 0 ?

The question is what is the complexities of the divide and conquer solution using master theorem ? and in T(R) = 3T(R/4) + f(R), what should be the f(R) ?

if it helps, this is my divide and conquer solution :

bool find_x_in_matrix(int x, int mat[3][3], int top_row, int top_col, int bot_row, int bot_col) {
if(top_row > bot_row || top_col > bot_col)
    return false;

int mid_row = (bot_row + top_row) / 2;
int mid_col = (bot_col + top_col) / 2;

if(mat[mid_row][mid_col] == x)
    return true;
else if(mat[mid_row][mid_col] > x) {
    return find_x_in_matrix(x, mat, top_row, mid_col, mid_row - 1, bot_col) ||
        find_x_in_matrix(x, mat, top_row, top_col, mid_row-1, mid_col-1) || 
        find_x_in_matrix(x, mat, mid_row, top_col, bot_row, mid_col-1);
}else if(mat[mid_row][mid_col] < x) {
    return find_x_in_matrix(x, mat, top_row, mid_col + 1, mid_row, bot_col) || 
        find_x_in_matrix(x, mat, mid_row + 1, top_col, bot_row, mid_col) || 
        find_x_in_matrix(x, mat, mid_row + 1, mid_col + 1, bot_row, bot_col);       
}
}

edit to clarify solution :

algorithm : 1. compare the middle element of the matrix to the search value 2. if the value equals m(i,j) return true 3. if the value is smaller, search the value in top right, top left, bottom left of matrix 4. if the value is larger, search the value in top right, bottom right, bottom left of the matrix

Answer 1

I dont know if this right, but i'm using case 2 of the master theorem

T(R) = 3T(R/4) + theta(1)

f(R) = theta(1) = theta(R) = theta(R^(log4(3)))

f(R) = theta(R^(log4(3))) = theta(R^(log4(3)) * logk(R)) is true with k = 0, so the time complexity is :

T(R) = theta(R^(log4(3)) * log(R)) = theta(R^0.8 * log(R))