1
$\begingroup$

Suppose we have an $N \times N \times N$ 3-d sorted array meaning that every row,column, and file is in sorted order. Searching for an element in this structure can be done using $O(N^2)$ comparisons. However are $\Omega(N^2)$ comparisons needed in the worst-case? For an $N \times N$ 2-d sorted array I recall a proof that $\Omega(N)$ comparisons are needed; I'm having trouble seeing how to extend to the 3-d case though

$\endgroup$
  • 1
    $\begingroup$ Note that you can use LaTeX to typeset mathematics in a more readable way. See here for a short introduction. Also, what have you tried towards extending the bound? $\endgroup$ – Raphael Apr 14 '14 at 18:13
1
$\begingroup$

Let's suppose that the array is indexed using $\{1,\ldots,N\}$, and assume for simplicity that $N$ is odd. Divide the cells in the array into three parts: $$ \begin{align*} X &= \{ (i,j,k) : i+j+k < 3 \tfrac{N+1}{2}, \} \\ Y &= \{ (i,j,k) : i+j+k = 3 \tfrac{N+1}{2}, \}, \\ Z &= \{ (i,j,k) : i+j+k > 3 \tfrac{N+1}{2}, \}. \end{align*} $$ Consider a 3D array $A$ with $A(i,j,k) = -\infty$ for all $(i,j,k) \in X$ and $A(i,j,k) = \infty$ for all $(i,j,k) \in Z$ (you can think of $-\infty,\infty$ as stand-ins for large negative and positive numbers). We claim that any such array is sorted. Indeed, suppose for example that $i_1 < i_2$ and $j,k$ are given. If $i_1 + j + k < 3\frac{N+1}{2}$ then $A(i_1,j,k) = -\infty \leq A(i_2,j,k)$. If $i_1 + j + k \geq 3\frac{N+1}{2}$ then $A(i_1,j,k) \leq \infty = A(i_2,j,k)$.

It follows that you cannot rule out that a finite number is in $A$ without checking all entries in $Y$ (formally this can be proved using an adversary argument). The number of entries in $Y$ is at least $N^3 / (3N-2) = \Omega(N^2)$.

The same idea extends to give a lower bound of $N^{d-1}/d$ in the $d$-dimensional case.

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