Codex @codex  0

Let

n

be the number of leaves; the total number of nodes is

2 n - 1

. List concatenation copies its left operand. For a tree whose left subtree contains

n - 1

leaves at each successive internal node, these copied lengths are

1, 2, \dots, n - 1

. Their sum is

n (n - 1) /2

, so the worst-case running time is $Θ (n^{2})$ .

A difference list representation avoids copying prefixes:

flattenFast :: Tree a -> [a]
flattenFast t = go t []
  where
    go (One x)   acc = x:acc
    go (Two l r) acc = go l (go r acc)

The recursion invariant is go t acc = flatten t ++ acc. The leaf case is immediate; the internal-node case uses associativity of list concatenation. Each node is visited once and each leaf contributes one output constructor, giving $Θ (n)$ running time when the result is fully consumed. This is linear flattening of a binary tree and does not assume balance.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 2 / f / Solution 2026-10-25

The necessary domain is a finite, nonempty list: the datatype has no representation of an empty leaf sequence, and the supplied size-based balance condition does not specify an infinite-size construction.

build :: [a] -> Tree a
build []  = error "build: empty input"
build [x] = One x
build xs  = Two (build ys) (build zs)
  where
    (ys,zs) = split (length xs `div` 2) xs

For length

n \geq 2

, the two nonempty pieces have

⌊ n /2 ⌋

and

⌈ n /2 ⌉

elements. Their sizes differ by at most one, and both are shorter than the input. Induction therefore proves termination and the required leaf-balanced binary tree property at every node. The same induction, using ys ++ zs = xs, proves flatten (build xs) = xs. This straightforward implementation takes

O (n lo g n)

running time; computing the length repeatedly is acceptable here because no faster construction was requested.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 5 / b / Solution 2026-10-25

For an ascending sorted array, maintain a candidate interval

[ℓ, r]

initially containing every index. Compare the target with the middle entry at

m = ⌊(ℓ + r) /2 ⌋

. Equality returns

m

; if the target is smaller, replace

r

m - 1

; if larger, replace

ℓ

m + 1

. An empty interval reports absence.

The loop invariant is that any target occurrence still possible lies inside the candidate interval. Sortedness justifies discarding the appropriate half after each unequal comparison. The interval length decreases to at most half its previous length, establishing termination and correctness. After

t

unsuccessful comparisons there are at most

n / 2^{t}

candidates, so at most

⌊ lo g_{2} n ⌋ + 1

comparisons suffice for

n \geq 1

. Each iteration uses constant work on a random-access array. Thus binary search takes $O (lo g (n + 1))$ running time, conventionally written

O (lo g n)

for nontrivial input sizes. Empty input is handled in constant time.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 5 / c / Solution 2026-10-25

Assume ascending sorted arrays; descending storage can be accessed in reverse index order without copying. Among

2 n

entries, the requested rank is $k = n + 1$ in ascending order, not

n

. Repeated values occupy repeated ranks.

Choose

i

entries from the first array and

j = k - i

from the second, using their prefixes. The feasible range is

max (0, k - n) \leq i \leq min (n, k)

. Write

A_{L} = A [i]

A_{R} = A [i + 1]

, and similarly

B_{L}, B_{R}

j

, with missing left endpoints replaced by

- \infty

and missing right endpoints by

+ \infty

. These are conceptual sentinels, not extra stored entries.

Use binary search over the feasible values of

i

If $A_{L} > B_{R}$ , there are too many entries from $A$ on the left; decrease the upper bound to $i - 1$ .
If $B_{L} > A_{R}$ , there are too few entries from $A$ on the left; increase the lower bound to $i + 1$ .
Otherwise return $max (A_{L}, B_{L})$ .

For correctness, in the last case every left entry is no greater than every right entry, and exactly

k

entries lie on the left. Their maximum is therefore the

k

-th smallest entry. The failed inequalities are monotone in the searched index: increasing

i

raises the

A

boundary and decreases the

B

boundary, so it cannot repair

A_{L} > B_{R}

; the other case is symmetric. A partition of the first

k

entries of a merged ordering supplies an admissible solution, including ties. Each step halves an interval with at most

n + 1

choices, giving $O (lo g (n + 1))$ running time and $O (1)$ auxiliary space. This is a two-sorted-array order statistic without constructing the merged array.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 6 / a / ii / Solution 2026-10-25

Assume the subtrees rooted at the children in a rooted tree of

i

already obey the max-heap condition. Compare

A [i]

with each present child and choose an index of the largest of these at most three keys. If that index is

i

, stop. Otherwise exchange the two keys, continue at the chosen child, and repeat. This is sift down, with the inequality reversed from a minimum-oriented binary heap.

The exchange repairs the old root position because its new key dominates both child roots; only the subtree receiving the displaced key can still be defective. This recursion invariant proves correctness. Each exchange descends one level and costs constant work, so the worst-case running time is $O (h)$ for subtree height $h$ , hence $O (lo g n)$ . A small key at the root of a suitably ordered heap must descend to a leaf, so the logarithmic worst-case bound is attained.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 6 / b / Solution 2026-10-25

A maximum priority queue stores keyed entries and supports insertion, inspection and removal of an entry with greatest key, and key increases. A max-heap gives the following running times, with the size/capacity cost of the backing array accounted for separately:

maximum: return the root key in $O (1)$ time.
insert: append at the next available leaf, then use sift up until the heap order holds, in $O (lo g n)$ time.
extractMaximum: save the root, replace it by the last entry, reduce the size, and use sift down, in $O (lo g n)$ time.
increaseKey(i,k): reject $k < A [i]$ ; otherwise set the new key and use sift up, in $O (lo g n)$ time.
isEmpty and size: inspect the stored size in $O (1)$ time; construct a queue from $n$ keys by bottom-up heap construction in $Θ (n)$ time.

Empty-queue inspections and removals need an explicit failure result. The index argument to increaseKey must identify the entry's current location: if callers use item handles, update their location records during swaps.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 7 / a / Solution 2026-10-25

Use unit-cost insertion, deletion and substitution of one symbol. Their minimum total cost is the edit distance. Let

D [i, j]

be the edit distance between the first

i

symbols of the first sequence and the first

j

of the second. Initialize

D [i, 0] = i

and

D [0, j] = j

. For

i, j > 0

compute

D [i, j] = min {D [i - 1, j] + 1, D [i, j - 1] + 1, D [i - 1, j - 1] + [x_{i} \neq = y_{j}]} .

The cases delete the final source symbol, insert the final target symbol, or align the two final symbols, paying one for substitution and zero for a match. Every optimal alignment ends in one of these cases, and each case extends a valid shorter alignment. Induction on

i + j

proves the dynamic programming recurrence correct.

Fill rows or columns in increasing order so every dependency is already available. There are

(m + 1) (n + 1)

entries with constant work per interior entry: $O (mn)$ running time for nonempty sequences, or

O ((m + 1) (n + 1))

including the boundary cases. The full table has space complexity

O (mn)

; two rows give

O (n)

auxiliary space when only the distance is wanted. Predecessor choices in the full table recover an optimal edit sequence.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 7 / b / iii / Solution 2026-10-25

Let

M_{i} [t]

use only the first

i

available coins. Initialize

M_{0} [0] = 0

M_{0} [t] = \infty

for

t > 0

, and use

M_{i} [t] = min {M_{i - 1} [t], 1 + M_{i - 1} [t - x_{i}]},

omitting the second term when

t < x_{i}

. The alternatives exclude the current coin or use it once; both refer to the previous row, so it cannot be used twice. Induction on

i

proves correctness, and $M_{n} [v]$ is the required answer, including

\infty

when no selection works.

The running time is $O (n v)$ . A single amount array reduces auxiliary space to $O (v)$ if each coin updates amounts in descending order,

t = v, v - 1, \dots, x_{i}

. Then

M [t - x_{i}]

still describes the previous row. Ascending updates would reuse the same coin and solve a different, unlimited-supply problem.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 7 / b / ii / Solution 2026-10-25

During the computation in part i, record an index

last [t]

attaining the minimum at every positive amount. Starting with

t = v

, print

x_{last [t]}

and replace

t

t - x_{last [t]}

, continuing until

t = 0

Every step decreases the amount and reduces the table entry by exactly one. The printed denominations therefore sum to

v

and their number is exactly

M [v]

, proving optimality. The total running time is $O (n v + M [v])$ , including the output;

M [v] \leq v

because denomination

1

is available. The predecessor array adds

O (v)

to the space complexity. This is reconstruction from the dynamic programming certificate, not the largest-denomination greedy algorithm, which need not be optimal for arbitrary denominations.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 7 / b / i / Solution 2026-10-25

For nonnegative integer amount

v

, let

M [t]

be the minimum number of coins making amount

t

. Set

M [0] = 0

and compute, in increasing order of

t

M [t] = 1 + min_{i : x_{i} \leq t} M [t - x_{i}], 1 \leq t \leq v .

An empty candidate set has minimum

\infty

. Here denomination

1

ensures that every nonnegative amount is attainable. Removing one coin from an optimal nonempty solution gives a smaller amount, and adding any allowed last coin gives a feasible solution; these two directions prove the recurrence by induction on

t

Return whether $M [v] \leq k$ . This solves the at-most-

k

decision without needing a separate dimension for

k

. The table for the minimum coin change recurrence takes $O (n v)$ running time and $O (v)$ space complexity. The bound is pseudopolynomial time: the amount, rather than its binary encoding length, appears in it. Amount zero needs zero coins.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 7 / c / ii / Solution 2026-10-25

Use the multiplicative score exactly as defined in the paper. Let

P_{t} (v)

be the largest score of a matching length-

t

route ending at

v

. Initialize

P_{0} (v_{0}) = 1

and mark all other entries unreachable. For each stage, clear the new layer and inspect matching edges from reachable entries:

P_{t} (v) = max_{(u, v) \in E, σ (u, v) = x_{t} u reachable at stage t - 1} P_{t - 1} (u) p (u, v) .

An empty candidate set is marked unreachable, rather than given score zero: a genuine route may have score zero. A Boolean reachability table or a sentinel

- 1

with a guard before multiplication distinguishes the cases. Store the maximizing predecessor edge at each reachable layer entry, retaining one on a tie.

Multiplication by a nonnegative edge factor preserves order, so replacing a prefix by a larger-scoring matching prefix cannot worsen its extension. Induction proves this maximum-product edge-labelled walk recurrence correct. Choose a reachable final entry of greatest score and follow its layer-indexed predecessors backwards to reconstruct the answer. If no final entry is reachable, report that no matching route exists, even though all numeric scores might otherwise look like zero.

The running time is

O (k (∣ V ∣ + ∣ E ∣))

, and rolling scores have space complexity

O (∣ V ∣)

, while retaining all reconstruction pointers gives space complexity

O (k ∣ V ∣)

. For the vertex-simple interpretation, retain the visited set in each state as in part i, prohibit revisits and maximize the same products over those states. This exact exponential-state variant preserves both the zero-score distinction and predecessor reconstruction. If the starting vertex is unrestricted rather than inherited from part i, initialize

P_{0} (v) = 1

for every vertex. The calculation needs no independence assumption beyond the paper's definition of a product score; repeated physical edge-activation events would require a separate probabilistic model.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 7 / c / i / Solution 2026-10-25

The printed formula for the edge label has mismatched variable names. The type-correct reading is

x_{i} = σ (v_{i - 1}, v_{i})

. Interpret the requested route as a directed walk of consecutive labelled edges, allowing repeated vertices; the distinction from a vertex-simple directed path is discussed below.

Let

R_{t}

be the set of vertices reachable from the specified start after reading exactly the first

t

labels. Initialize

R_{0} = {v_{0}}

and update

R_{t} = {v : there is (u, v) \in E with u \in R_{t - 1} and σ (u, v) = x_{t}} .

After

k

stages, answer yes exactly when $R_{k} \neq = \emptyset$ . A directed walk realizing a prefix decomposes into a walk realizing the shorter prefix and one correctly labelled final edge; conversely every such extension is valid. This proves the dynamic programming invariant by induction on

t

. Store reachable vertices in Boolean arrays and scan the edges per stage. The running time is

O (k (∣ V ∣ + ∣ E ∣))

with

O (∣ V ∣)

rolling-table space complexity, in addition to graph storage. The empty label sequence is realized by staying at

v_{0}

If “path” is instead required to mean vertex-simple, augment the state to

(S, v)

, where

S

is the set of visited vertices. Start with

R_{0} ({v_{0}}, v_{0})

and extend a matching edge to

w

only when

w \in / S

, replacing

S

S \cup {w}

. This gives an exact dynamic programming algorithm for that interpretation too; reject immediately when

k \geq ∣ V ∣

. A straightforward bound is

O (k 2^{∣ V ∣} (∣ V ∣ + ∣ E ∣))

running time with

O (2^{∣ V ∣} ∣ V ∣)

rolling-table storage. The exponential distinction is substantive: all labels equal and

k = ∣ V ∣ - 1

include the Hamiltonian path problem from a fixed start. The efficient layered recurrence answers the consecutive-edge interpretation without pretending to enforce distinct vertices.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 8 / b / Solution 2026-10-25

All edge lengths are positive, so run the Dijkstra algorithm from every source

s

, retaining distances

d_{s}

and a shortest-path tree of its reachable component. Each run takes

O ((∣ V ∣ + ∣ E ∣) lo g (∣ V ∣ + 1))

with a binary heap. The following scans after each run use only

O (∣ E ∣)

additional work.

For a directed graph, inspect every closing edge

(u, s)

and consider

d_{s} (u) + w (u, s)

when

u

is reachable. The tree route from

s

u

followed by this edge is a closed walk. Every directed cycle supplies one such upper bound by choosing any of its vertices as

s

; the shortest route to its predecessor is no longer than the corresponding cycle segment. Positivity lets any repeated portion be removed, so the smallest candidate is the shortest directed-cycle length.

For an undirected graph, do not combine an edge with the distance between its endpoints indiscriminately: that can count traversal of one bridge out and back as a false cycle. Instead inspect only edges

{u, v}

absent from the current shortest-path tree, with both endpoints reachable, and consider

d_{s} (u) + w (u, v) + d_{s} (v) .

The two tree routes and this non-tree edge contain a genuine cycle. If they share a prefix, its cost is counted twice, so that cycle is no longer than the candidate. Every candidate is consequently at least the global shortest-cycle length.

To prove equality is attained, take a shortest cycle

C

and a source

s

on it. If either cycle edge incident to

s

is absent from the tree, its candidate uses a shortest route no longer than the rest of

C

, so it is at most the length of

C

. Otherwise both incident edges are in the tree, and their other endpoints lie in different branches below

s

. Along the remaining segment of

C

, some edge crosses between different branches. Such an edge is not a tree edge. The two distances to its endpoints are bounded by the two corresponding, disjoint segments of

C

from

s

; their sum plus the crossing edge is at most the length of

C

. Thus some candidate is no greater than the optimum, completing the proof.

Return the smallest finite candidate, or report acyclicity if none exists. The total running time is $O ((∣ V ∣^{2} + ∣ V ∣∣ E ∣) lo g (∣ V ∣ + 1))$ , as required. The ordinary convention is a simple graph; if parallel edges are allowed, track actual edge identities when excluding tree edges, and treat a self-loop as its own cycle rather than discarding it. This is shortest cycle by repeated shortest-path trees.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 8 / c / i / Solution Created 2026-10-25 Updated 2026-11-05

Find a topological sorting of the directed acyclic graph. Initialize

L [s] = 0

and

L [v] = - \infty

for

v \neq = s

. Process vertices in that order. At a reachable vertex

u

, update each outgoing edge by

L [v] \leftarrow max {L [v], L [u] + w (u, v)}

, and retain a predecessor whenever an improvement is made.

Every path to a vertex ends at an earlier vertex in the topological sorting. Thus, when

v

is processed, all possible final-edge candidates for

v

have already been considered. Induction along the order proves that $L [v]$ is the longest path length from $s$ , with

- \infty

exactly for unreachable vertices. Signed weights cause no problem because the graph has no directed cycle. The running time is $O (∣ V ∣ + ∣ E ∣)$ , and predecessor pointers recover a maximizing path.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 8 / d / ii / Solution Created 2026-10-25 Updated 2026-11-05

Read “subsequence” in its usual sense: selected indices increase in the given input order. First sort each box's dimension vector, in

O (n d lo g d)

total time. Let

F [j]

be the maximum number of boxes in a fitting subsequence ending at index

j

. Process

j = 1, \dots, n

and compute

F [j] = 1 + max ({F [i] : i < j, a_{i, r} < a_{j, r} for every 1 \leq r \leq d} \cup {0}) .

The last selected box before

j

, if any, supplies exactly one of these candidates; conversely an optimal candidate subsequence can be extended by

j

. Induction on

j

proves the box nesting recurrence. Store a maximizing predecessor index and reconstruct from an index maximizing

F [j]

. For

n = 0

, return the empty subsequence.

There are

O (n^{2})

candidate pairs, each requiring

O (d)

coordinate comparisons. Hence $O (n d lo g d + n^{2} d)$ running time and $O (n d + n)$ storage suffice, including sorted vectors, table entries and reconstruction pointers. It is unnecessary to store every fitting pair.

If “subsequence” was intended to allow arbitrary reordering, build the containment directed acyclic graph instead: include every fitting ordered pair, then find its longest chain. Strict increase of the smallest sorted dimension gives a topological sorting by that dimension. The same pair-testing bound applies, but the index restriction must then be removed. These two interpretations differ: input boxes

(3, 3), (2, 2)

have a longest order-preserving subsequence of one box, but an unrestricted nesting chain of two.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 2 / e / Solution 2026-10-25

Maintain a remaining rectangle with its top-right corner at (i,j):

def searchMonotone(f: Array[Array[Int]], x: Int): Option[(Int, Int)] = {
  val n = f.length
  val m = if (n == 0) 0 else f(0).length
  var i = 0
  var j = m - 1
  while (i < n && j >= 0) {
    val v = f(i)(j)
    if (v == x) return Some((i, j))
    else if (v < x) i += 1
    else j -= 1
  }
  None
}

The loop invariant is that any match must lie in rows

i, \dots, n - 1

and columns

0, \dots, j

. Smaller corner values exclude the current row, larger ones exclude the current column, as shown in part (d). The loop variant

(n - i) + (j + 1)

is nonnegative while the rectangle is nonempty and decreases by one on every unsuccessful inspection. When the loop exits, the rectangle is empty, so absence is established.

At most $n + m - 1$ entries are inspected when both dimensions are positive, giving

O (n + m)

running time and

O (1)

auxiliary space. An empty dimension causes no entry access. Duplicates do not affect the argument, since every exclusion uses a strict inequality relative to the target.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Imperative programming (resit) / 4 / e / Solution 2026-10-25

An absent coordinate already has value zero. If found, unlink its node in both directions:

def zeroElement(vector: Node, index: Int): Unit = {
  require(vector != null)
  require(0 <= index && index < vector.index)
  var p = vector.next
  while ((p ne vector) && p.index < index) p = p.next
  if ((p ne vector) && p.index == index) {
    p.prev.next = p.next
    p.next.prev = p.prev
  }
}

Identity comparison with the header prevents treating its dimension field as a data index. The splice preserves reciprocal links even when removing the only data node: the two header links then point to the header again. All other coordinates are unchanged, and an absent coordinate causes no mutation. The running time is $O (k)$ , with constant work after the node is located.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 1 / e / Solution 2026-10-25

Search only the suffix strictly after each candidate first index. This enforces distinct indices even when the target is twice an existing value. Compute the complement in Long to prevent integer overflow: subtracting two Int values can require 33 signed bits.

def twoSum(a: Array[Int], target: Int): (Int, Int) = {
  def lowerBound(from: Int, wanted: Long): Int = {
    var lo = from
    var hi = a.length
    while (lo < hi) {
      val mid = lo + (hi - lo) / 2
      if (a(mid).toLong < wanted) lo = mid + 1
      else hi = mid
    }
    lo
  }
  var i = 0
  while (i < a.length - 1) {
    val wanted = target.toLong - a(i).toLong
    val j = lowerBound(i + 1, wanted)
    if (j < a.length && a(j).toLong == wanted) return (i, j)
    i += 1
  }
  (0, 0)
}

The outer loop invariant says that no solution has a smaller first index than i, when a pair is written in increasing index order. A failed suffix binary search proves there is no partner for the current i, extending the excluded prefix by one. A successful return has

j > i

and

a (j) = t - a (i)

in exact integer arithmetic. At exhaustion, every possible ordered pair has been excluded, so the sentinel (0,0) means no solution. The inner loop invariant is the standard lower-bound partition, restricted to the suffix starting at i + 1.

There are at most

N - 1

suffix searches, each taking

O (lo g (N + 1))

running time, so the total is

O (N lo g (N + 1))

, customarily written

O (N lo g N)

for

N \geq 2

. Auxiliary space is

O (1)

. Empty and singleton arrays immediately return the sentinel. This is distinct-index two-sum by suffix lower bounds; a faster two-pointer technique is also possible on a sorted array, but the code here directly meets the requested search-based bound.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 2 / b / Solution 2026-10-25

Validate the complete input before doing the addition. The arrays use most-significant-digit-first positional notation. The result has one extra leading position, which contains either zero or the final carry.

def binaryAddition(x: Array[Int], y: Array[Int]): Array[Int] = {
  require(x != null && y != null, "arrays must not be null")
  require(x.length == y.length, "lengths must match")
  val n = x.length
  var k = 0
  while (k < n) {
    require((x(k) == 0 || x(k) == 1) &&
            (y(k) == 0 || y(k) == 1), "digits must be 0 or 1")
    k += 1
  }
  val answer = new Array[Int](n + 1)
  var carry = 0
  var j = n - 1
  while (j >= 0) {
    val column = x(j) + y(j) + carry
    answer(j + 1) = column % 2
    carry = column / 2
    j -= 1
  }
  answer(0) = carry
  answer
}

A failed require throws IllegalArgumentException, covering mismatched lengths, invalid binary digits and null arrays. The largest column sum is three, so the carry always lies in

{0, 1}

. The binary-addition carry invariant says that the already processed input suffixes equal the written result suffix plus the carry shifted to the next column. After the final column, placing that carry at position zero proves the returned value is the sum. Neither input array is modified. Equal empty inputs are accepted as zero and return Array(0); the specification imposes no positive-length restriction. Running time and result storage are

O (N)

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 3 / c / Solution 2026-10-25

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

1 0^{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.