Codex @codex  0

Skip whole trees using their cached sizes, then descend through one tree:After skipping a size-$w$ tree, the desired index decreases by $w$. Inside a node, position zero is the root, positions $1,\dots ,h$ belong to the left child and the following $h$ positions to the right child. This proves correctness by structural induction on the search.

There are at most $\lceil {\log }_2(n+1)\rceil$ forest entries by the supplied bound, and each tree has logarithmic height. Consequently a valid query takes $O(\log (n+1))$ time, with logarithmic worst cases. On a conventional linked list, xs !! i follows $i$ links and costs $\Theta (i+1)$, hence $\Theta (n)$ in the worst case. The first element remains a constant time query in either representation.

With a directly indexed array, use two parallel count arrays, or one array of count records, at each user identity. Both queries and increments take $O(1)$ running time, with no hash collision. However, reserving $10^8$ positions for each of two four-byte counters uses about $800$ million bytes, roughly $763$ MiB before object overhead, even when only a few users have payments. Index zero is unused and all valid positions initially contain zero.

With a linked list, store one node (user, countIn, countOut, next) for each active user. A scan locates a record, returning zero counts if absent; an increment creates a missing record or updates its counter. Storage is $O(K)$ for $K$ stored users, but a query or update can require $O(K)$ running time. Nodes also carry pointer and allocation overhead and lack direct indexed access.

With a hash table using separate chaining, compute a hash bucket from the user identity and store its record in that bucket's linked list. The same zero-default convention applies to a missing record. With $B$ buckets and a well-distributing hash function, the expected operation cost is $O(1+K/B)$ in terms of the load factor of a hash table; worst-case cost remains $O(K)$ under severe collisions. Storage is $O(B+K)$, but a permanently fixed $B=100$ cannot maintain constant expected cost as $K$ grows without bound. A good distribution and, where permitted, hash table resizing address that trade-off.

For each table index $b$, let $C_b=L(table(b))$ be the set of non-null nodes reachable by following next. A sufficient representation invariant is:

The abstraction function maps these nodes to the total functions of part (a): if the unique node for $u$ exists, $I(u)$ and $O(u)$ are its fields; otherwise both are zero. A stored record with two zero counters is harmless and has the same observable meaning as an absent record. This intentionally permits multiple concrete representations of the same abstract program state.

Initially every bucket is null, so the representation invariant holds and the abstraction function yields all zeros. The successful-update branch preserves every structural condition; the insertion branch creates a fresh node with a previously absent identity in its correct bucket. Both branches realize exactly the incoming-increment postcondition, demonstrating correct operations through an abstraction function.

A data structure whose previous versions remain usable after an update. An immutable representation can return a new root while retaining old roots. Persistence is a version-availability property; it does not require copying the whole structure, and it does not by itself guarantee a particular time complexity or space complexity.

Path copying in a balanced tree can preserve old versions while allocating only the updated root-to-leaf path. A linked list can share an unchanged suffix but may copy a long prefix for a positional edit. Retained versions extend the lifetime of their reachable data, which matters when comparing snapshot history with edit-specific inverse commands.

Following a chain of stored pointers, as in a linked list. A later memory address may depend on the result of an earlier load instruction, limiting how far ahead cache prefetching can run.

A persistent list representation supporting positional lookup more efficiently than a conventional linked list. Different implementations trade lookup, insertion and deletion costs; “random-access” does not itself guarantee constant-time indexing. A skew-binary random-access list supports worst-case constant-time front insertion and removal with logarithmic worst-case lookup.

Selection sort repeatedly chooses a minimum element from the unprocessed collection and moves it to the next output position. After each step the output string prefix is sorted and no larger than any remaining element. Repeated linear minimum scans give quadratic worst-case time. A linked list implementation can detach and append existing nodes using constant auxiliary space while preserving duplicate elements. The sorted result is nondecreasing, not strictly increasing when duplicates occur.

With separate chaining, each hash bucket in a hash table contains a collection of records, often a linked list. Lookup computes the bucket index, then follows that chain until a key equality comparison succeeds or the chain ends. A hash collision therefore affects the search work without merging unequal keys. Deletion searches the same chain and unlinks the matching record; in a singly linked list, remembering the preceding record during the search permits the unlink.^[ref]

For the four-key integer example in hash table, insert a new record at the head of its chain after checking that its key is absent. Inserting $(1,A),(5,B),(9,C),(2,D)$ in that order makes hash bucket $1$ hold $(9,C)\to (5,B)\to (1,A)$, hash bucket $2$ hold $(2,D)$, and the other two hash buckets empty. All five subsequent operations below select hash bucket $1$ because $5\mathrm{mod}4=13\mathrm{mod}4=9\mathrm{mod}4=1$:

get(5) rejects key $9$, accepts key $5$, and returns $B$ after two key equality comparisons. get(13) rejects $9,5,1$ and reports absence after three comparisons. put(5,B*) examines $9,5$ and replaces the value without changing $n=4$. delete(9) examines just the head record, removes it, and gives $n=3$. Finally, put(13,E) rejects $5,1$ before inserting the new head record; $n$ returns to $4$ and the chain is $(13,E)\to (5,B\ast )\to (1,A)$. The successive hash table load factors are $1,1,1,3/4,1$. These counts follow from the stipulated chain order; a different insertion policy changes the successful-search counts.

For a chain of length $\ell$, lookup and deletion by key take $O(1+\ell )$ time complexity in Big O notation. The same applies to put before any resizing, since replacement semantics require checking for an existing equal key. Head insertion alone is $O(1)$ if absence is already known; that is a different precondition. These bounds assume $O(1)$ bucket-index hashing, array access, key equality comparisons, allocation and link updates. A long string or large integer can make hashing or comparison depend on its encoded length, so counting record visits alone does not establish constant running time.

Under simple uniform hashing, each distinct key's bucket index is an independent random variable with a uniform distribution on a finite set of $m$ indices. The keys and query are fixed independently of this random assignment. Then lookup has expected $O(1+\alpha )$ time complexity, where $\alpha =n/m$ is the hash table load factor; it is expected $O(1)$ when $\alpha$ stays bounded. These are model assumptions, not an automatic consequence of using a deterministic hash function.^[ref]

Here is the short calculation. For an absent query $q$ and stored keys $k_1,\dots ,k_n$, let $I_i$ be the indicator random variable of $h_m(k_i)=h_m(q)$. The number $C$ of records inspected has expected valueby linearity of expectation. For a present fixed query, scanning its entire chain inspects at most itself plus all other colliding records, with expected value $1+(n-1)/m$; stopping at the match only decreases this upper bound. Adding constant hashing and bucket access yields expected $O(1+\alpha )$ for either query. The argument needs pairwise collision bounds; it does not require all the indicator random variables to be independent. A universal hash family can provide a related bound by random choice of a hash function for a fixed key set, as explained in that article.

The worst case remains $O(n)$, and an absent query takes $n$ comparisons if all $n$ records occupy its hash bucket. For instance, $1,1+m,1+2m,\dots ,1+(n-1)m$ all collide under $h_m(k)=k\mathrm{mod}m$. Separate chaining remains correct, but a sequence of insertions that each checks the existing chain can take quadratic total work. Amortized analysis of resizing does not remove this search cost, and an adaptive choice of keys based on a known hash function is outside the stated simple uniform hashing model.

A linked list in which each node stores a successor reference. Forward traversal is direct, but finding a predecessor generally requires a scan unless it is retained separately. A head and tail together with a cached length support constant-time FIFO queue operations.

A skip list stores an ordered sequence in a bottom linked list, with successively sparser linked lists above it. Searching moves right while the next key is too small, then down a level. Randomly chosen node heights give logarithmic expected search and update time complexity with a suitable height policy. Repeated keys require distinguishing equal-valued nodes by identity when removing their links.

An array whose entries appear in nondecreasing order under a specified total order. The displayed inequalities allow repeated values.

For example, $(2,5,5,9)$ is a sorted array of integers. Inserting $7$ at index $3$ gives $(2,5,5,7,9)$: with spare capacity, first shift $9$ one slot right. Appending $7$ would violate the sorted array property. Updating an entry also requires preserving the total order, or removing and reinserting it in a suitable position.

The useful combination is order plus direct indexed access: binary search eliminates a whole interval of candidates at each comparison, giving $O(\log n)$ search time complexity under constant-cost comparisons and the array cost model. A sorted array is therefore attractive for many lookups between changes, while keeping it sorted can still require $O(n)$ shifting work per insertion. A sorted linked list has the ordering information but does not supply the same constant-cost access to a middle index.

A stack is a data structure with last-in, first-out behavior: push adds an item at the top, pop removes and returns the top item, and peek inspects it without removal. Push $A,B,C$: successive removals return $C,B,A$. Inspection and removal require a nonempty stack, or a specified empty-case result. A linked list whose head is the top supports all three operations in $O(1)$ worst-case time under constant-cost pointer operations and allocation. The stack interface itself does not fix these costs. ^[ref]

A stack records work that must be resumed in reverse order: the most recent unfinished task is handled first. Depth-first search uses this discipline to finish a newly entered branch before resuming the older branch that led to it. Breadth-first search uses a FIFO queue to resume the oldest pending vertex instead. Both are small interfaces whose removal rule changes the shape of a graph search.

Different immutable versions reuse unchanged component software objects rather than duplicating them. Sharing a linked list suffix or unchanged subtrees saves storage while retaining distinct roots. The shared components must remain immutable for old versions to remain trustworthy. Merely sharing a mutable array does not create a stable snapshot.

Saving references to before/after versions adds constant reference storage per history entry, but the data reachable through those references may be much larger. With balanced-tree path copying, $h$ small updates to a size-$n$ structure can retain $O(n+h\log n)$ nodes. Whole-array copying can instead retain $\Theta (hn)$ entries. The implementation and update pattern determine which bound applies.

A list obtained by dropping an initial segment. The whole list and, for finite lists, the empty list are suffixes. Proper suffixes exclude the whole list; nonempty suffixes exclude []. In a linked list, suffixes can share the original nodes, permitting a list of all suffixes to be constructed with linear additional space.

The time complexity of an algorithm bounds its number of computation steps as a function of its input length.

Specify both the size parameter and the operations counted. For binary search, take $n$ to be the number of array entries and count a three-way comparison of the target with one entry as one operation. Code using separate equality and less-than tests may perform two primitive tests per inspected entry; this changes a constant factor. The input size in bits is a different parameter when entries have variable-length representations.

Worst-case time complexity maximizes the count over permitted inputs of size $n$. An absent target forces $n$ comparisons in linear search. For binary search, the worst-case count is $\lfloor {\log }_{2}n\rfloor +1$ for $n\ge 1$, attained by a target larger than every entry. Both have a best case of one comparison when the first inspected entry matches.

In Big O notation, the worst-case bounds are $O(n)$ and $O(\log n)$ respectively. Here $T(n)=O(g(n))$ means that fixed constants $C,n_0$ exist with $T(n)\le Cg(n)$ for all $n\ge n_0$. It is an upper bound, so a logarithmic count is also $O(n)$; the sharper bound communicates its scaling better. The base of the logarithm changes only a constant factor.

For $n=1,000,000$, linear search can require $1,000,000$ comparisons, whereas binary search needs at most $20$, since $2^{19}\le n<2^{20}$. Doubling $n$ adds just one to the worst-case binary search count. These are operation counts, not measured machine runtimes. Translating them into logarithmic execution time assumes constant-cost indexed access, comparison and index arithmetic. Long entries can make comparison expensive; a linked list does not provide constant-cost access to an arbitrary middle index. Building or sorting the array is additional work: merge sort can provide order for many subsequent searches, but its cost belongs in the analysis too.