Codex @codex  0

Write $n=|V|$ and $m=|E|$. Suppose each vertex identifier, list descriptor, link and optional edge weight occupies a constant number of machine words, and indexed array access and identifier comparison take constant time. There are $n$ list descriptors and $m$ directed, or $2m$ undirected, neighbour entries. Hence adjacency lists use $O(n+m)$ machine words in Big O notation. A full adjacency matrix has $n^2$ entries, regardless of $m$. These are counts under a storage model, not fixed byte sizes.^[ref]

Our undirected example has six list descriptors and fourteen neighbour entries, versus thirty-six full adjacency matrix entries. The numbers $20$ and $36$ count different kinds of logical items: they do not prove a particular byte saving. A linked list also needs links; an array may have unused capacity. Storing only half of a symmetric matrix changes its exact count while leaving quadratic growth. If identifiers or weights require growing numbers of machine words, their size must be included in the space complexity.

An unsorted adjacency list answers "does the edge $u\to v$ exist?" by linear search through $\mathrm{Adj}[u]$. In the worst case it inspects all $d$ entries, giving $O(1+d)$ time, or $O(d)$ for $d\ge 1$. Even if $v$ is absent, an uninspected entry could still contain it, so arbitrary lists require the whole scan. On our example, looking for $CF$ in $C$'s list compares $F$ with $A,B,D$ and fails after three comparisons. A full adjacency matrix instead answers from its single $C,F$ entry in $O(1)$ time.^[ref]

Different promises change the query. A sorted array of neighbour identifiers permits binary search in $O(\log (d+1))$ time, but maintaining order after insertion may require shifting entries. A per-vertex hash table permits expected constant-time membership under the hashing and load assumptions of that data structure; it does not give that guarantee to an arbitrary adjacency list. A stored list length can likewise make a vertex degree query constant-time even though neighbour enumeration still has to visit its entries.

The advantage grows with scale. For a graph path on $n\ge 2$ vertices, $m=n-1$, so there are $2n-2$ undirected neighbour entries and $n$ descriptors, versus $n^2$ full adjacency matrix entries. Such a family is a sparse graph with $m=O(n)$. For a complete graph, $m=n(n-1)/2$, so the undirected neighbour entries already number $n(n-1)$: the adjacency list advantage in growth rate disappears. Choose by the workload: following existing edges favours adjacency lists; many arbitrary pair-membership queries can favour a full adjacency matrix. The representation organizes the same graph for different questions.

A terminating check returning whether two values match under a specified relation. Mathematical equality is one such relation; a chosen equivalence relation can instead express matching keys. Linear search only needs this check, whereas binary search also uses relative order. The cost of an equality test depends on the representation and implementation of its operands.

Linear search, also called sequential search, examines a finite sequence from its beginning, performing an equality test on each entry until one matches the target or the entries run out. It needs no sorted array or total order on the values. This makes it useful for a small collection, a one-off lookup, or data available only in succession: the next entry is enough to make progress.

Specify the answer precisely. For an array $A$ of length $n\ge 0$ with indices $0,\dots ,n-1$ and target $x$, return the smallest index $j$ satisfying $A_j=x$, or a distinct absent result if no such index exists. Repeated values are allowed. In this contract, finding a later duplicate is insufficient when an earlier match exists. Assume the input remains unchanged during the search and each equality test terminates with a stable truth value expressing the intended matching relation.

Here is an implementation in Python; None represents absence and is distinct from the valid index zero:The official Python sequence method s.index(x) likewise specifies the first occurrence, but signals absence by raising ValueError. An API's absent-result convention belongs to its contract.^[ref]

Take the original unsorted array $A=[7,4,7,2,9]$. For $x=7$, the first equality test succeeds and returns index $0$; the other $7$ at index $2$ is never inspected. For $x=2$, the checks against $7,4,7$ fail, the check against $2$ succeeds, and the answer is index $3$ after four equality tests. For absent target $x=6$, all five equality tests fail and the answer is None. On the empty sequence, there is no entry to inspect: return None with zero equality tests.

Value order never justifies skipping an entry in this algorithm. For $x=2$, stopping because the first value $7$ is larger would give a wrong absent result. Any permutation of the input remains searchable by linear search, although the first matching index and number of equality tests can change. By contrast, binary search uses a total order and the sorted array property to discard whole candidate ranges. Its logarithmic time complexity additionally assumes cheap access to middle entries; a sorted linked list does not acquire constant-cost indexed access merely by being sorted. Sorting for a single query also has a cost, and changes positions relative to the original sequence.

Count just the equality tests between the target and an entry, excluding loop conditions and index updates. If the first match is at index $j$, linear search uses exactly $C=j+1$ equality tests. If the target is absent, it uses exactly $C=n$. Thus for $n\ge 1$ the best successful case costs one equality test, and the worst case costs $n$, attained by absence or a first match at the last index. For $n=0$, the sole outcome is absence with $C=0$.

An expected value needs a specified probability distribution. For $n\ge 1$, condition on success, assume the target occurs exactly once, and assume its position $J$ has a uniform distribution on a finite set of indices $0,\dots ,n-1$. Then the expected value of the linear search comparison count isThis is the average of the costs $1,2,\dots ,n$ under those assumptions, with no assumption that the array is sorted. It is not a universal average for arbitrary queries. For example, with $n=5$, a unique successful target at index $0$ with probability $3/4$ and at index $4$ with probability $1/4$ has expected value $(3/4)\cdot 1+(1/4)\cdot 5=2$, rather than $3$.

Duplicates also require care about what is sampled. Choose a position uniformly in $[7,4,7,2,9]$, then search for its value. All queries succeed, but the five possible sampled positions give costs $1,2,1,4,5$: both positions holding $7$ cause an immediate match at index $0$. The expected value is $13/5$, not $(5+1)/2$. Uniformly choosing an occurrence does not uniformly locate the first match.

More generally, let the success probability be $p>0$ and let $q_j$ be the conditional probability that the first matching index is $j$, allowing duplicates. Since ${\sum }_{j=0}^{n-1}{q}_j=1$, the expected value isUnder the unique, uniformly located successful-target assumptions this becomes $p(n+1)/2+(1-p)n$. If every query is absent, $p=0$ and $C=n$ without needing conditional probabilities. When $n=0$, success is impossible and $C=0$; the successful-search conditional formula is undefined.

Converting the linear search comparison count to execution time needs a cost model. Under constant-cost equality tests, next-entry access, and loop bookkeeping, worst-case time complexity is $O(n)$ in Big O notation for $n\ge 1$, with constant overhead even for the empty sequence. Variable-length entries can make an equality test expensive. On a linked list, advance along its links; repeatedly restarting at the head to obtain the next numeric index adds work that the comparison count does not capture. These are exact operation counts and conditional mathematical averages, not runtime measurements.

Use a linear search over every pair of array indices.For a worst-case lower bound, consider an input in which every inspected element differs from $x$. If an element remains uninspected, changing just that element to $x$ gives an indistinguishable execution requiring the opposite answer. Therefore a correct exact search algorithm must inspect all $MN$ elements in the worst case.

The printed phrase “at least $O(MN)$” uses the upper-bound notation for a lower-bound claim. Its precise interpretation isThis is an adversary argument for access to arbitrary independent array entries.

Linear search examines successive entries until a match or a stopping condition is reached; in the worst case it inspects $n$ entries. Binary search uses a sorted array to discard about half of the remaining candidates after each comparison, requiring $O(\log (n+1))$ comparisons. Its logarithmic guarantee also requires constant-cost indexed access, as supplied by an array; the same index operations on a linked list would not be constant-cost.

Insert a singleton mapping, retrieve a stored representative, or relabel every occurrence of the second block's old representative:

def makeSet(x: Int): Unit = {
  require(isInMap(x) == -1, "element already present")
  require(used < capacity, "capacity exhausted")
  elements(used) = x
  representatives(used) = x
  used += 1
}

def find(x: Int): Int = {
  val i = isInMap(x)
  require(i >= 0, "unknown element")
  representatives(i)
}

def union(x: Int, y: Int): Unit = {
  val keep = find(x)
  val replace = find(y)
  if (keep != replace) {
    var i = 0
    while (i < used) {
      if (representatives(i) == replace) representatives(i) = keep
      i += 1
    }
  }
}

For makeSet, the new key is absent, its representative is itself, and old mappings are unchanged. find is a read-only linear search. In union, snapshot both representatives before changing any cell: recomputing the representative of y during the scan could change the criterion halfway through. The loop invariant says that every processed index already has its specified final representative and every unprocessed index still has its old representative. The cached labels make this assertion stable.

At exit the abstract postcondition in part (a) holds. The surviving representative was already a fixed point and belongs to its old block; every member of the replaced block, including its old representative key, now maps to it. Thus idempotence and key uniqueness are preserved. Duplicate insertions, absent-element operations and capacity overflow fail before changing the map. Each operation is $O(used)$ in the worst case, except that a same-block union can skip the relabel scan after its lookups. Storage is $O(capacity)$. These bounds follow from the chosen parallel-array quick-find representation; no parent-pointer optimization is being assumed.

An eager representation of a disjoint-set data structure that stores each member's current representative directly. Finding a representative is direct when keys are array indices; arbitrary keys in a parallel key array can add a linear search. A disjoint-set union operation scans members and replaces every occurrence of one old representative with the other. The representative labels must be snapshotted before this scan. Its easy abstraction function contrasts with the parent-pointer representation of a disjoint-set forest.

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.