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!
he said we could merely reduce it by a factor of 3/4 for each step
I didn't. I was just talking about @yang.zheng.904's proposal. Which is doing that.