Lower bound on number of comparisons needed to search for a number in a sorted 3-d array

Question

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

Answer 1

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.