Young Tableau

Hi All,
The other day me, sanjeet, and pranjal were discussing a few questions ( or puzzles ) which are likely to be asked in technical interviews. One of the question that was asked to someone in google was about finding out a specific element in an n x n Young Tableau.

Let me first define, what a young tableau is. It is an m x n array with the following property.

for all j = 1 to n-1, A[p][i] <= A[p][i+1]
and for all , i = 1 to m-1 , A[i][q] <= A[i+1][q] It is easy to see that following statement holds for a young tableau.

1. For any sub-matrix of a young tableau, the top-left element is the smallest element within that sub-matrix.
2. For any sub-matrix of a young tableau, the bottom-right element is the largest element within that sub-matrix.

Now, the problem is to find out a given element within an n x n young tableau.

----
Method -1
----

Start with the top-right element of the tableau. Compare this element e with the element to be found x.
if e > x then
discard the column in which e appears. ( Because e is the first(smallest ) element of that column.
else
discard the row in which e appears.
end if.
Repeat this exercise until the element is found or the tableau is exhausted.

It is easy to see that time complexity of Method-1 is O(n). As at every step we will discard either row or column which will take at most 2n steps.

---------
Method - 2
---------
Do a binary search over the diagonal of the tableau. If we find the desired element x then we are done. If not, we will have two element u and v where u <> u is the bottom-right element and v is the top-left element. The elements that we will discard at each step would be at least half of the elements in the original matrix.
Here is why,

i^2 + (n-i)^2 function is minimum where i=n/2. With i=n/2 the value of the function is (n^2)/2.

Now, if we do the analysis with respect to number of elements.
T(n^2) = 2T((n^2)/4) + logn

or

T(m) = 2T(m/4) + 0.5 logm

Solution of this recurrence, turns out to be O(m^(0.5)) = O(n). So, there is no improvement over the complexity as compared to the first method. Besides, this second method fails when the sub-matrices that were discarded were not square. In which case, the remaining two sub-matrices will not be square either.
----
Method 3
------
Compare the central element e with the desired element x.
if e > x then discard the bottom-right quadrant of the tableau.
else discard the top-left quadrant of the tableau.

Now , we are left with three sub-matrices of the size n/2 x n/2.

The recurrence would be

T(n) = 3T(n/2) + O(1).

Solving it would give us n^(log_2 3) = n^1.585. It turns out that even though in Method-1 you discard n elements and in this method you discard (n^2)/4, the complexity does not favour Method-3. Anyways, it was a good exercise to do this analysis.