Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

An $n \times n$ Young tableau is an $n \times n$ matrix of distinct integers, with each row and each column sorted in increasing order.

Now, we are given an $n \times n$ Young tableau $T$ and an integer $x$ which is known to appear in $T$. The goal is to find $x$ in $T$. That is, find $1\leq i,j \leq n$ such that $T_{ij}=x$. In order to do so, only comparisons are allowed. The result of a comparison is one of $\leq,\geq,=$. Comparisons are allowed between elements of $T$ or between $x$ and an element of $T$.

How many comparisons are needed in the worst case to find $x$ (asymptotically)?

Obviously, you can't do better than $O(\log n)$ comparisons because each comparison gives $O(1)$ bits of information, while there are $O(\log n)$ bits of information in the pair $i,j$.

On the other hand, the best algorithm I could think of to find $x$ uses $O(n)$ comparisons. It works as follows:

  1. $i \leftarrow 1, j \leftarrow n$
  2. While $T_{ij} \neq x$:
    a. If $T_{ij} < x$ Then $i \leftarrow i+1$
    b. If $T_{ij} > x$ Then $j \leftarrow j-1$
  3. Return $i,j$

In each iteration we rule out either a row or a column, so we are done after $O(n)$ comparisons.

Can we close the gap between $O(\log n)$ and $O(n)$?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

It is clearly not possible to do better then $O(n)$. Even if I give you the additional information that the smallest $\binom n2$ entries fill the upper-left triangle of that size and the largest $\binom n2$ entries similarly fill the bottom-right triangle, that leaves the diagonal given by $i+j=n+1$ for the remaining $n$ entries, and they could be positioned according to any permutation of $n$. If $x$ is one of those $n$ entries the problem then comes down to finding $x$ in an unsorted array of length $n$, and this obviously cannot be done in less thatn $O(n)$ comparisons (you just need to stumble upon $x$).

share|improve this answer
    
Thank you very much. I posted a follow-up question: math.stackexchange.com/questions/294043/… –  user3533 Feb 3 '13 at 23:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.