Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 4

Computational complexity theory studies the resources needed by an algorithm as a function of input size, after specifying the resource and computational model. For example, time complexity may count comparisons, and space complexity may count stored words. Worst-case time complexity $T(n)$ is the greatest cost among inputs of size $n$; best-case and average costs are different measures.

An upper bound guarantees that a cost is no greater than the stated bound. A lower bound guarantees that it is no smaller. For a problem, an algorithm can establish an upper bound on what is achievable, while a problem lower bound must apply to every eligible algorithm in the chosen model. Bounds need not be tight. Concisely,

For eventually nonnegative functions $T,f,g$, Big O notation and Big omega notation meanThese are asymptotic upper bounds and lower bounds up to positive constant factors. The notation $T(n)=O(f(n))$ conventionally expresses membership in the class $O(f)$, rather than equality of two numerical functions.

Use binary search. Maintain an inclusive candidate interval [lo,hi], initially [0,n-1]. Compare the target v once with the middle entry; a ternary comparison returns less than, equal to, or greater than. Equality ends successfully. Otherwise sortedness permits discarding the middle entry and the entire half on the wrong side:

lo := 0; hi := n-1;
WHILE lo <= hi DO
  mid := lo + (hi-lo) DIV 2;
  IF v = S[mid] THEN RETURN TRUE
  ELSIF v < S[mid] THEN hi := mid-1
  ELSE lo := mid+1
  END
END;
RETURN FALSE

The two written tests represent one ternary comparison whose result is then inspected. The loop invariant says that every occurrence of v, if any, lies in the candidate interval. Initially it is true. The order comparison and sortedness preserve it after either discard. If the interval becomes empty, the loop invariant proves absence.

A failed comparison reduces a candidate interval of size $m$ to at most $\lfloor m/2\rfloor$. For $n\ge 1$, at most $\lfloor {\log }_{2}n\rfloor +1$ comparisons are needed; an empty input needs none. HenceThe claim counts comparisons. Indexed access to an array also makes elapsed running time logarithmic in the usual model; a linked list representation would not give the same access cost.

Use two indices, initially the first and last positions of the ordered sequence. The two elements occupy distinct positions, so continue only while i < j:

i := 0; j := n-1;
WHILE i < j DO
  t := S[i] + S[j];
  IF t = x THEN RETURN TRUE
  ELSIF t < x THEN i := i+1
  ELSE j := j-1
  END
END;
RETURN FALSE

The loop invariant is: a solution exists in the original input if and only if one exists with both indices in [i,j]. If S[i]+S[j] < x, then S[i]+S[k] <= S[i]+S[j] < x for every k <= j, so index i cannot belong to a remaining solution. If the sum is too large, S[k]+S[j] >= S[i]+S[j] > x for every k >= i, so index j cannot belong to one. This proves preservation of the loop invariant. Equality gives the desired pair, and an interval with fewer than two positions contains none.

Every unsuccessful iteration decreases the loop variant j-i by one, so there are at most $n-1$ sum comparisons and only constant space is needed. Duplicate values are permitted if they occupy distinct positions. Under exact constant-cost real arithmetic and endpoint access,