# Searching a Young tableau for a collection of numbers

This question is a follow up on: Searching a Young tableau.

The previous question was "How many comparisons are needed to find an element $x$ in an $n \times n$ Young tableau of distinct elements (asymptotically)?".

The algorithm presented in the question itself shows an upper bound of $O(n)$ while the accepted answer gives a matching lower bound of $\Omega(n)$.

The reasoning behind the lower bound is essentially that even in the special case where the tableau is $-\infty$ above the diagonal and $+\infty$ below the diagonal, and even if this this extra information is given to the inquirer, the elements on the diagonal can be ordered arbitrarily and thus the problem is at least as hard as finding an element in an unsorted array of $n$ elements.

Now, to an enhanced version of this question:

Given an $n \times n$ Young tableau of distinct elements and list of $n$ distinct elements $x_1,\dotsc,x_n$ which are all known to appear in the table. What is the smallest number of comparisons needed to find all $n$ elements in the table?

The allowed types of comparsions are between elements in the list, between elements in the table, and between and element in the list and an element in the table.

Searching for the elements in the list one-by-one requires $O(n^2)$ comparisons. Yet, the previous lower bound does not generalize to give an $\Omega(n^2)$ bound because matching between two unsorted lists of $n$ elements each may be done in $\Theta(n\log n)$ time by sorting both lists.

-
The implication of your last sentence is not clear to me. Each of the $x_i$ could be in a separate interval of $O(n/2)$ values, and each of those intervals could be independently permuted on a separate diagonal of that length. Now how are you going to locate those $n$ values among those $nO(n/2)=O(n^2)$ locations, without visiting each location at least once? – Marc van Leeuwen Feb 4 '13 at 4:49
@MarcvanLeeuwen: I meant that if you assume again that all values above/below the diagonal are $-\infty$/$\infty$ respectively, then all the values you're looking for are on the diagonal and can be matched to the $x_i$-s using only $O(n\log n)$ comparisons. – user3533 Feb 4 '13 at 9:30
@MarcvanLeeuwen: I'm trying to complete your comment to a complete proof of an $\Omega(n^2)$ lower bound. Take $x_i=i$ for every $i$. Order the diagonals you mentioned from the upper one to the lower. On the $i$-th diagonal, place numbers in the range $[i,i+1)$, with exactly one of them equal to $i$. Complete the tableau by placing very small numbers above the upper diagonal and very large ones beneath it. The choice of where on the $i$-th diagonal to put the number $i$ is completely arbitrary, and thus in the worst case all elements of all those diagonals must be accessed. Seems right? – user3533 Feb 4 '13 at 10:41