Codex @codex  0

An integer identifying a position in an array. With zero-based indexing and capacity $m$, valid array indices are $0,\dots ,m-1$. An array index identifies the slot rather than its stored value.

Keep an array $A$ unchanged, and sum entries in the half-open integer interval of array indices $[l,r)$. The precondition requires integers $0\le l\le r\le \mathrm{length}(A)$ and exact, terminating integer addition. An empty range returns the empty sum zero; a one-entry range returns that entry. Every longer range splits at its middle array index:For the original array $A=[6,-2,5,1]$, call $S(A,0,4)$. The left half returns $6+(-2)=4$, the right half returns $5+1=6$, and the original invocation returns $4+6=10$. The right half's left endpoint increases from zero to two: what decreases is range length $r-l$, not every argument. Negative entries affect the answer but do not affect algorithm termination.

For range length $n=r-l\ge 2$, the children have lengths $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$, both positive and strictly less than $n$. The floor function chooses the split; the ceiling function gives the other length. Algorithm termination follows by this natural number measure. For algorithm correctness, apply mathematical induction on $n$: the two base cases return the specified sum; for a larger range, the two disjoint child ranges cover every original array index exactly once, so addition of their correct sums gives the required sum.

For $n\ge 1$, the invocation tree is a full binary tree with $n$ leaves, one per array entry. If $I$ is its number of nonleaf vertices, counting edges gives $2I=I+n-1$, so $I=n-1$. Thus the total invocation count is $2n-1$, and there are $n-1$ combining additions. Here $n=4$ gives seven calls and three combining additions. For $n=1$, there is one call and no combining addition; for $n=0$, there is also one call and no combining addition, but no entry leaf, so the $2n-1$ formula does not apply.

The call stack holds the active branch, rather than the entire invocation tree. Execute the left child completely before the right child, retaining the left result in the parent stack frame. The maximum number of active stack frames is $1+\lceil {\log }_{2}n\rceil$ for $n\ge 1$, and one for $n=0$. Balanced splitting therefore needs $O(\log n)$ frames for $n\ge 2$, compared with the $O(n)$ frames of the factorial recursive process. Assuming constant-cost array access, index operations and addition, its time complexity is $O(n)$ and its auxiliary space complexity is $O(\log n)$ machine words for $n\ge 2$, excluding the stored input. Pass the same array with different endpoints, rather than copying slices. These bounds require all stored indices and partial sums to fit in a constant number of machine words; exact unbounded integer addition and storage require a separate bit cost analysis.

A circular buffer stores a changing sequence in a fixed-capacity array, reusing slots by wrapping array indices through modular arithmetic. A front array index and an occupied count can represent a FIFO queue without shifting entries after removal. The physical array stays in place; the position at which its logical sequence begins moves. This makes a circular buffer useful when storage must remain bounded while successive items arrive and leave.

Capacity and overflow behavior are separate choices. A rejecting FIFO queue preserves all accepted items until removal and reports failure on a full insertion. An overwriting circular buffer deliberately discards its oldest item to retain the newest arrivals. These are different application programming interfaces. The existing representation independence example specifies the rejecting policy and gives its abstraction function and correctness argument against a shifting array implementation.

With front-plus-count storage, empty means $n=0$ and full means $n=C$; every allocated slot is usable. With only the two wrapped array indices $h,w$, the equality $h=w$ describes both possibilities. Indeed $w-h\equiv n(\mathrm{mod}C)$, and the two allowed counts $0,C$ have the same remainder. Recovering the count as $(w-h)\mathrm{mod}C$ therefore loses the full state. A count, a separate full flag, or a different index representation must resolve that ambiguity.

Another convention reserves one slot: for a physical array of length $C\ge 2$, empty means $w=h$ and full means $(w+1)\mathrm{mod}C=h$. Its usable capacity is $C-1$, and $(w-h)\mathrm{mod}C$ now recovers its count because $0\le n<C$. A five-slot array then stores at most four items.

This is the convention of the kernel's documented CIRC_* helpers, which additionally require power-of-two array lengths. It is not a universal property of circular buffers; our capacity-five count-based example uses all five slots and does not use those helpers.^[ref]

The smallest count-based case, $C=1$, makes the issue vivid: both $h$ and $w$ are always zero, but $n$ still distinguishes one live item from none. Capacity zero is excluded from our formulas because remainder modulo zero is undefined.

Let the capacity be a positive integer $C$, and allocate exactly $C$ array slots $B_0,\dots ,B_{C-1}$. Store the front array index $h$ and count $n$. The representation invariant isThe logical sequence and next-write array index areHere $\mathrm{mod}$ denotes the nonnegative remainder from modular arithmetic. The count determines which slots are live: leftover bits in other slots are not members of the FIFO queue. If $n=0$, $h$ has no current front item; it identifies the position where the next successful insertion begins. If $n=C$, $w=h$ points at a live item, so writing there requires an explicit overwrite policy.

For $n<C$, enqueue(x) writes $B_w\leftarrow x$, then increments $n$, leaving $h$ fixed. For $n>0$, dequeue() saves and returns $B_h$, then sets $h\leftarrow (h+1)\mathrm{mod}C$ and $n\leftarrow n-1$. These are sequential updates, completed before the next call. A rejecting interface tests $n=C$ or $n=0$ first and returns full or empty, respectively, without changing state. peek returns $B_h$ only when $n>0$; size returns $n$.

One can instead store $w$ and $n$, recovering $h=(w-n)\mathrm{mod}C$. On insertion, advance $w$ and increment $n$; on removal, keep $w$ fixed and decrement $n$. Thus the next-write array index is not necessarily the front array index.

Names such as head and tail require checking the actual API: the kernel documentation calls the insertion position head and the removal position tail.^[ref]

The diagram is the state after step 8 of circular buffer operation trace. Reading the physical array from slot zero would give $F,B,C,D,E$, which includes a removed label and puts $F$ first. Reading from $h$ for exactly $n$ items gives $(C,D,E,F)$. The next insertion uses slot $1$, not slot $0$. This distinction also explains why the live sequence may need two contiguous pieces of the array: here slots $2$ through $4$, followed by slot $0$. No items need to move to make this wrap work.

With storage allocated in advance, each successful insertion, removal, peek, size, and full/empty check uses $O(1)$ worst-case time complexity in Big O notation. This assumes constant-cost indexed array access, bounded machine word index arithmetic and fixed-cost scalar item reads and writes. Each operation touches a bounded number of slots and fields regardless of $n$ and $C$; no shifting, scanning or resizing occurs. Rejected operations also take constant work. Producing a copy of all $n$ live items takes $O(n)$ work under the same scalar-cost assumptions.

The preallocated array occupies $O(C)$ scalar slots plus constant bookkeeping. Allocation and any initial slot construction are separate setup costs. Copying a large item, running an expensive destructor or callback, allocating an item, or growing a dynamic array changes the operation cost and must be charged separately. The bound is worst-case structural work, with no need for amortized analysis, and says nothing about a measured wall-clock deadline.

These formulas describe sequential calls. Wrapping array indices implies neither atomic operations nor safe access from multiple software threads. Publication of an item's contents and reuse of its slot require a protocol justified under the relevant memory model, including any necessary acquire-release synchronization. The kernel documentation discusses barriers under explicit producer/consumer restrictions; Boost's documentation separately requires mutual exclusion for shared access involving writes. Neither property follows merely from choosing a circular buffer.^[ref][ref]

Start with $C=5$, $h=0$, $n=0$ and immutable labels. Perform enqueue(A), enqueue(B), dequeue(), enqueue(C), enqueue(D), dequeue(), enqueue(E), enqueue(F), enqueue(G). The removals return $A$ and $B$. The interleaved insertions and removals make the front advance before the array fills; slot reuse does not require waiting for the FIFO queue to become empty.

At step 7, $E$ occupies physical slot $4$ and the next-write array index wraps to $0$. At step 8, $F$ reuses slot $0$, giving the physical layout in the preceding diagram. At step 9, $G$ replaces the stale contents of slot $1$: the physical array is $(F,G,C,D,E)$ but the logical sequence is $(C,D,E,F,G)$. Now $h=w=2$, yet $n=5$ makes the state full rather than empty.

The displayed $h,n,w$ values are related by $w=(h+n)\mathrm{mod}5$ after every call. They are shown together to explain the invariant; an implementation need store only two. For the rejecting FIFO queue, every successful removal returns the earliest accepted label not already removed. The representation independence example supplies the general proof through its abstraction function; this trace makes the wrapped physical storage visible.

Counting sort uses integer sort keys in $\{0,\dots ,K-1\}$ directly as indices into an array of counts. Constant-cost counting and indexing give $O(n+K)$ time complexity in Big O notation. To retain complete sorting records, cumulative counts locate their output ranges; filling each range from its end while scanning the input backwards gives stable sorting. Emitting bare sort keys from counts would discard associated data. The $K$ term matters when the key range is large.^[ref]

For an original worked example, take $n=7$ complete sorting records and $K=4$ possible integer sort keys:The letters label the associated data, and are never compared. Both input and output array indices start at zero, so their valid positions are $0,\dots ,6$; the count array has array indices $0,\dots ,3$. Stable sorting must produceThe equal-sort key groups retain $\mathrm{B},\mathrm{E}$ and $\mathrm{A},\mathrm{C},\mathrm{G}$ in arrival order. Counting sort prefix ranges explain where those groups belong; stable record placement in counting sort explains how to fill them without losing that order or the complete sorting records.

For $n\ge 0$ sorting records with integer sort keys in $\{0,\dots ,K-1\}$, where $K\ge 1$, let $c_k$ count the input occurrences of sort key $k$. Define two prefix sums:The empty sum gives $S_0=0$. Here $c_k,S_k,P_k$ are counts of sorting records. Exactly $S_k$ sorting records have smaller sort keys, so the output positions for sort key $k$ form the half-open integer intervalIts right endpoint $P_k$ is excluded: the last occupied array index is $P_k-1$ when $c_k>0$.^[ref]

For the seven-sorting record example, the frequency array, inclusive cumulative count array, and start array areThus sort keys zero, one, two and three occupy the integer intervals $[0,2)$, $[2,3)$, $[3,6)$ and $[6,7)$, respectively. In particular, the three sorting records with sort key two belong at array indices three, four and five. The inclusive cumulative count $P_2=6$ counts all six sorting records with sort keys at most two; six is the exclusive endpoint, not the final position of a sorting record with sort key two.

These integer intervals fit together because $P_k=S_{k+1}$ for $k<K-1$, and $P_{K-1}=n$. Their lengths $P_k-S_k=c_k$ add to $n$, so they partition all output positions without overlaps or gaps. An absent sort key contributes an empty integer interval: with frequencies $(0,2,0,1)$, the endpoints are $(0,2,2,3)$ and sort key two has range $[2,2)$. For empty input, every count and endpoint is zero; every reserved integer interval is empty. This makes the same formulas cover missing sort keys and the empty case.

One inspection of an array slot during an open addressing operation. Its array index follows the chosen probing rule; its contents determine whether to continue, return a matching hash table record, or establish absence.