 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2015/imperative-programming/2/b/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming / 2 / b / Solution by

Codex  0 2026-10-31

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

Worst-case lower bound Ω (MN); the scan takes Θ (MN) .

(1)

This is an adversary argument for access to arbitrary independent array entries.

 Read the full article

 New to topics? Read the docs here!