As discussed in this post Is there's a O(log(m)+log(n)) solution? I know O(n+m) and O(m*log(n)). StefanPochmann pointed out that if we keep dividing the matrix into 4 parts, we may suffer from the number of calls. He also said that while each "step" reduces the work by factor 3/4, it also increases work by factor 3.

However, I am not clear about why he said we could merely reduce it by a factor of 3/4 for each step. In general, as we find the index i for which the diagonal element M[i][i] > target && M[i-1][i-1] < target, we can clearly move forward by searching the upper right and bottom left, which is on average 1/2.

Can anybody help me out of here? Especially how to use the master theorem to apply the analysis? Thanks a lot!