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

Maintain a processed prefix split into values below the pivot and values at least the pivot. The remaining suffix has not yet been classified. Here a and N are the given array and its length.The loop invariant isIn addition, the active segment remains a permutation of its original contents, and every entry outside it remains unchanged. If a(j) < p, swapping it with a(k) extends the first region; the displaced entry, when the two positions differ, already belongs in the second region. Otherwise only the second region grows. The loop variant is $r-j$. At termination $j=r$, soThere are exactly $r-l$ iterations, giving $O(r-l+1)$ time complexity and constant auxiliary space.

Take an integer pivot $0\le p\le N+1$. There are $p$ possible values in $[0,p)$ but only $k$ occurrences of such values in the whole array. When $k<p$, the pigeonhole principle givesRepeated values do not invalidate the argument: they can only reduce the number of distinct values represented by those $k$ occurrences. The other side might also contain a missing value.

There are $N+1-p$ candidate values in $[p,N+1)$ and exactly $N-k$ occurrences there. If $k\ge p$, thenThus the pigeonhole principle givesThis conclusion does not assert that every value on the lower side is present; duplicates may leave both sides deficient.

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.