0
$\begingroup$

Let us call matrix $A$ ascending if $A_{kl}\ge A_{ij}, i \le k, j \le l$ for every $k$ and $l$. Given a number $x$ prove that determining whether $x$ is in an ascending matrix or not takes more than $n$ comparisons.

I understand that finding number in sorted array takes at least $\log(n)$ comparisons, but I don't know where to start with the matrix.

$\endgroup$
1
$\begingroup$

It takes at least $n$ comparisons to check whether a given number $x$ is contained in an unsorted list $L = (x_1, x_2, \ldots, x_n)$ with $n$ elements. Create a matrix $A$ by writing the elements from $L$ on the diagonal $(A_{n1}, A_{(n-1)2}, \ldots, A_{2(n-1)},A_{1n})$. Fill the upper left triangle of the matrix with a small number $a$ which is smaller than all elements of $L$, and the lower right triangle with a large number $b$ which is larger than all elements of $L$. You obtain the following ascending matrix $$ A = \begin{pmatrix} a & \cdots & \cdots & a & x_n \\ \vdots & & \kern1mu\raise1mu{.}\kern3mu\raise8mu{.}\kern3mu\raise14mu{.} & x_{n-1} & b \\ \vdots & \kern1mu\raise1mu{.}\kern3mu\raise8mu{.}\kern3mu\raise14mu{.} & \kern1mu\raise1mu{.}\kern3mu\raise8mu{.}\kern3mu\raise14mu{.} & \kern1mu\raise1mu{.}\kern3mu\raise8mu{.}\kern3mu\raise14mu{.} & \vdots \\ a & x_2 & \kern1mu\raise1mu{.}\kern3mu\raise8mu{.}\kern3mu\raise14mu{.} & & \vdots \\ x_1 & b & \cdots & \cdots & b \end{pmatrix} $$ If you could check whether $A$ contains $x$ with less than $n$ comparisons, then you could also perfrom this check on $L$. This is not possible.

$\endgroup$

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.