Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 1 / c / Solution

Use missing-value search by deficient value intervals: halve the candidate value interval, and apply array partitioning only to the array segment whose entries lie in that interval.The loop invariant is $0\le l\le r\le N$, $0\le lo<hi\le N+1$, andMore precisely, the segment contains all occurrences of original values in $[lo,hi)$, and the complete array remains a permutation of its original state. The occurrences statement is essential: absence from the final segment must imply absence from the original array.

After array partitioning, let $m=r-l$, $W=hi-lo$, $m_L=k-l$, and $W_L=p-lo$. If $m_L<W_L$, retain the left side. Otherwise the right side hasoccurrences. Either choice preserves the strict deficiency and the all-occurrences condition. The positive integer width $hi-lo$ decreases, proving termination. At width one, the active segment has fewer than one entry and is empty. ThereforeFor the time complexity, after $t$ splits the width is at most $\lceil (N+1)/2^t\rceil$, and the scan length is smaller than that width. Summing over the $O(\log (N+1))$ levels gives a geometric series plus logarithmic overhead, hence $O(N+1)$ overall, conventionally $O(N)$ for $N\ge 1$. This proof bounds the retained occurrence count by the retained value width; it does not assume that each array partitioning splits the number of occurrences in half. The $N=0$ case returns zero immediately.