Find a elment in Matrix

Hey new question has occupied me this time, the question is like:
"We have matrix with rows and columns are sorted independently. And we are now asked to get some particular element"

One of the solution of this problem is assumed by taking a middle element to test and then proceed like binary search algorithm.
But.....
You know it will not have the same O(log n) order where n is matrix order as the case with usual binary search.

You my easily conclude that the complexity function with input size "n", can be defined as:
T(n) = 3*T(n/4) + constant

And by master method the complexity comes out

T(n) = n ^ (log43) = n^(1/4) = o(log n)

Ohhhh what happened!!!
I think its quite obivious as when you partition a space into 2 of which only one is to be searched which again be halved. But in this case you have partioned into 4 out which in worst case you may need to search in 3 spaces.
The beauty of getting order log n is not in saying that one part does not have the answer, but is in saying that the answer lies in only one partition.