Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 2 / c

Keep a deficient interval of possible values and only the array segment containing occurrences from that interval. This is missing-value search by deficient value intervals:The precondition is that every original entry lies in $[0,N+1)$. The loop invariant istogether with: every active entry lies in $[lo,hi)$, and every original occurrence with a value in that interval is in the active segment. The whole array remains a permutation of its initial contents. Initially these assertions follow from the precondition and $N<N+1$.

After array partitioning, the low subinterval has $k-l$ occurrences and $p-lo$ possible values. If it is deficient, retaining it preserves the loop invariant. Otherwise $k-l\ge p-lo$, while the original active count is strictly less than $hi-lo$; subtraction givesThus the high subinterval is deficient and retaining it also preserves the loop invariant. Discarded occurrences lie outside the new candidate interval. The loop variant is the positive integer $hi-lo$, which strictly decreases because the midpoint is strictly internal. At exit the interval has one possible value and fewer than one occurrence, so lo is absent from the entire original array. For $N=0$ the loop is skipped and zero is returned. The Long value bounds avoid overflowing $N+1$; every internal pivot is at most $N$, so its checked mathematical range fits Int.

For the time complexity, let $W_i$ be the interval width and $m_i$ its active occurrence count before iteration $i$. The loop invariant gives $m_i<W_i$, and binary search gives $W_{i+1}\le \lceil W_i/2\rceil$. Each two-way array partition costs $O(m_i+1)$. Until the width reaches one, the widths are bounded by $(N+1)/2^i+1$, so the total scan work is bounded by a geometric series plus $O(\log (N+1))$ loop overhead: $O(N+1)$ overall, hence $O(N)$ for positive $N$. Partitioning the full array again at every iteration would instead lose this bound. Auxiliary space complexity is $O(1)$.