5
$\begingroup$

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)$?

$\endgroup$

1 Answer 1

4
$\begingroup$

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$).

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .