= Solution
Use a <linear search> over every pair of <array indices>.
``
PROCEDURE SearchAll(x: INTEGER; VAR i, j: INTEGER): BOOLEAN;
VAR r, c: INTEGER;
BEGIN
FOR r := 0 TO M-1 DO
FOR c := 0 TO N-1 DO
IF f[r,c] = x THEN i := r; j := c; RETURN TRUE END
END
END;
RETURN FALSE
END SearchAll;
``
For a worst-case lower bound, consider an input in which every inspected element differs from $x$. If an element remains uninspected, changing just that element to $x$ gives an indistinguishable execution requiring the opposite answer. Therefore a correct exact <search algorithm> must inspect all $MN$ elements in the worst case.
The printed phrase “at least $O(MN)$” uses the upper-bound notation for a lower-bound claim. Its precise interpretation is
$$
\boxed{\text{Worst-case lower bound }\Omega(MN);\quad\text{the scan takes }\Theta(MN).}
$$
This is an <adversary argument> for access to arbitrary independent <array> entries.
Back to article page
