0
$\begingroup$

Given an array $A[1..n][1..n]$ such that $\forall i,j, k\ge i, l \ge j: \ A[k][l] \ge A[i][j]$ and a number $X$.

Prove there does not exist an algorithm which can determine if one of the elements of $A$ is $X$ and which makes less than $n$ comparisons.

Attempt

Each query "$A[i][j] > X?$" eliminates either $i \times j$ or $(n-i+1) \times (n-j+1)$ elements of $A$. I tried to prove that given arbitrary position of $X$, one cannot guarantee to eliminate the whole array with $n-1$ such queries. But I got stuck here.

$\endgroup$
1
$\begingroup$

You can use an "adversary argument" approach. You can think of any comparison-based algorithm as a black box. When you start it up, that box gives you a pair $i,j$ to check. You give the box the result of the comparison, and depending on whether $A[i][j]$ is greater/lower than $X$, the box will pick some new row/column to perform another comparison, until it finds an element that is equal to $X$, or is certain no element is equal to $X$.

As an adversary, your purpose is to show that whatever the method this black box uses, it is impossible to reach a definitive conclusion in less than $n$ comparisons. In other words, we're free to tell the box whatever comparison result we want, to force it to use at least $n$ comparisons. This is allowed as long as there exists some array $A$ and number $X$ that would indeed yield the comparisons results we feed to the box. So we need two things, first a strategy to answer the box to force it to use at least $n$ comparisons, and second, make sure that whatever our exchange with the box is, there always exists $A,X$ that fit that exchange.


Strategy

As you've observed, a comparison will remove some elements of the array from the discussion. It will either remove the elements that are above and to the left of $A[i][j]$, or those below and to the right. In particular, it gives absolutely no information about elements below and to the left, or above and to the right. To make use of this, a possible strategy is to force the black box to inspect every element of the second diagonal $A[i][n-i+1]$. Since there are $n$ such elements, the algorithm will use at least $n$ comparisons.

To do that, it's enough to consider three cases:

  1. If the query $A[i][j]$ belongs to the second diagonal, answer whatever you want.

  2. If the query $A[i][j]$ is above (and to the left of) the second diagonal, make the algorithm remove the elements above and to the left of $A[i][j]$.

  3. If the query $A[i][j]$ is below (and to the right of) the second diagonal, make the algorithm remove the elements below and to the right of $A[i][j]$.

With this, the box gets no information about the second diagonal unless it specifically queries an element on that second diagonal, thus forcing it to perform at least $n$ comparisons.


To conclude properly, you would have to show that there always exists $A,X$ that would fit the answers you give to the box, but I'll let you convince yourself of that on your own.

$\endgroup$
  • 2
    $\begingroup$ Simply put, this problem contains the problem of searching an element in a (regular 1D unordered) array (of length $n$) as a subproblem. Given an arbitrary array $B[1..n]$, we let $A[i][j]=B[i]$ if $i + j = n + 1$, $A[i][j]=-\infty$ (say) if $i + j < n + 1$ and $A[i][j]=+\infty$ otherwise - and the original problem becomes the problem of searching $X$ in $B$. $\endgroup$ – metamorphy May 24 '18 at 17:38
  • $\begingroup$ @metamorphy I think I like your explanation more than mine. Very clear and concise. $\endgroup$ – N.Bach May 24 '18 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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