= Solution
Maintain an <integer> `len`, initially zero, with `len = length xs`:
``
PROCEDURE Add(x: INTEGER);
BEGIN
ASSERT(len < N);
u[len] := x;
len := len+1
END Add;
``
The <precondition> is the abstract capacity condition. Appending at the first unused <array index> establishes $u[0..\mathrm{len})=xs'$ in constant <running time>.
If `get(k)` first applies a <comparison sort> to all $n=\mathrm{len}$ entries, the <comparison sorting lower bound> gives at least $\lceil\log_2(n!)\rceil=\Omega(n\log n)$ comparisons in the worst case. A <merge sort> or <heapsort> meets that order, after which indexing costs constant time:
$$
\boxed{\operatorname{add}:\Theta(1),\qquad\operatorname{get}\text{ by comparison sorting}:\Theta(n\log n)\text{ optimally in the worst case}.}
$$
This is a logarithmic factor worse than linear. The qualification to <comparison sorting> is necessary: merely saying that keys are <integers> does not prohibit <counting sort> for a bounded small range or <radix sort> under suitable machine-key assumptions. The printed assertion of an unavoidable superlinear bound needs the comparison model.
Back to article page
