Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 2 / b / Solution

Without order information, inspect entries one row at a time:

def searchUnordered(f: Array[Array[Int]], x: Int): Option[(Int, Int)] = {
  val n = f.length
  val m = if (n == 0) 0 else f(0).length
  var i = 0
  while (i < n) {
    var j = 0
    while (j < m) {
      if (f(i)(j) == x) return Some((i, j))
      j += 1
    }
    i += 1
  }
  None
}

The outer loop invariant excludes every entry in earlier rows; the inner one also excludes columns before j in the current row. Failed equality tests preserve these exclusions. The inner and outer loop variants are $m-j$ and $n-i$, respectively. A successful return identifies an actual match, while exhaustion excludes the entire array. At most $nm$ entries are inspected.

The source's “at least $O(nm)$” should be read as a worst-case $\Omega (nm)$ lower bound, using the correct asymptotic direction. If any entry were left unread on an all-nonmatching input, changing only that entry to $x$ would leave the observations identical while changing the answer. Thus every always-correct procedure needs $nm$ inspections in the worst case, and this algorithm achieves $\Theta (nm)$ entry inspections. Empty dimensions return absence; the asymptotic claim concerns nonempty arrays.