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.

An algorithm is a finite, precise procedure for transforming an input into an output.

Here "finite" refers to the description: a short algorithm can perform arbitrarily many steps on increasingly large inputs. Solving a computational problem additionally requires termination and the specified output on every permitted input. State assumptions explicitly: binary search requires a sorted array.

An algorithm is an idea that can have implementations in different programming languages. Its explanation should make three things visible: the permitted inputs, the rule for each step, and the meaning of the returned output. Algorithm correctness then separates finding the right answer from eventually finishing; time complexity asks how much work finishing requires.

A particularly useful design question is: what knowledge survives each step? In binary search, it is the location of every possible match inside the remaining candidate range. Writing that fact as a loop invariant turns an intuitive shortcut into a procedure whose discarded candidates can be justified. This often helps discover the algorithm, rather than merely check it afterward.

A binary heap represents a priority queue as a complete binary tree obeying a heap order. We use the minimum convention: the priority of every parent in a rooted tree is no greater than the priorities of its children in a rooted tree. Equal priorities are allowed. Each stored entry may be a record carrying a priority key; the numerical example below displays only keys. Reversing the inequalities gives the maximum convention.

The complete binary tree can be stored directly in a zero-indexed array $A=(A_0,\dots ,A_{n-1})$: read its levels from top to bottom, left to right. The root of a tree is at index $0$. The possible children in a rooted tree of index $i$ are at $2i+1$ and $2i+2$, and an index denotes a present entry only when it is less than $n$. For $i>0$, its parent in a rooted tree is at $\lfloor (i-1)/2\rfloor$, using the floor function. Thus the links of the complete binary tree are determined by arithmetic rather than separately stored pointers.

ConsiderThe children in a rooted tree of index $0$ have keys $5,3$; those of index $1$ have keys $9,7$; those of index $2$ have keys $8,4$. The six comparisons $2\le 5$, $2\le 3$, $5\le 9$, $5\le 7$, $3\le 8$, $3\le 4$ establish the heap order. At index $4$, the parent in a rooted tree is index $\lfloor (4-1)/2\rfloor =1$, carrying key $5$.

The array is visibly not a sorted array: $5$ precedes $3$, and $8$ precedes $4$. Nor is the last entry a maximum: it is $4$, whereas the maximum is $9$ at index $3$. The heap order compares ancestors and descendants, without imposing an order between separate branches. Nevertheless, following the graph path from the root of a tree to any entry gives a chain of nondecreasing priorities. This short argument proves that peek can return $A_0$, a minimum, without inspecting the other entries.

Insertion appends an entry to the array, preserving the shape of the complete binary tree, then uses sift up to repair the heap order. Insert key $1$ into the displayed binary heap. It is appended at index $7$, and exchanges with indices $3$, $1$, then $0$:The moving key follows $7\to 3\to 1\to 0$; the keys $9,5,2$ each move down one level. Only this chain needs repair.

Now apply extract-min. Save key $1$, move the last key $9$ to the root of a tree, and shorten the array to length $7$. Use sift down, always choosing the smaller of the present children in a rooted tree:First $9$ exchanges with key $2$ at index $1$, since $2<3$; then with key $5$ at index $3$, since $5<7$. At index $3$, the possible children in a rooted tree would be indices $7,8$, both outside the shortened array, so the process stops. The returned key is $1$, and the remaining binary heap is exactly the original one.

For a nonempty binary heap with $n$ entries, the deepest level is $\lfloor {\log }_{2}n\rfloor$, using the floor function and logarithm. Each exchange moves one level and uses only a bounded number of comparisons. The resulting time complexity bounds, expressed in Big O notation, are:

These bounds assume constant-cost indexed access, key comparisons and exchanges, and available array capacity for insertion. Allocating and copying a larger array is a separate cost. Empty and one-entry cases take constant work.

To build a binary heap, begin at index $\lfloor n/2\rfloor -1$ and work backwards. Entries without children in a rooted tree already obey the heap order. Each sift down, also called heapify down, starts with every present smaller rooted tree below it already repaired. Most entries are close to the bottom and can move very little; successively longer repair distances occur for geometrically fewer entries. Summing these distances gives $O(n)$ work, rather than charging $O(\log n)$ to every entry. MIT's notes give this bottom-up construction and contrast it with repeated insertion.^[ref]

The Dijkstra algorithm additionally needs to decrease the priority of an existing vertex when its tentative distance improves. Given its current index, lowering the key followed by sift up takes $O(\log n)$ time for $n\ge 2$. An indexed binary heap maintains a separate map from item identity to its current index and updates that map after every exchange. For vertices numbered in a fixed range, the map can be another array, giving constant-time index lookup. An ordinary unindexed binary heap supplies no such guarantee: locating an arbitrary item can require scanning $n$ entries. Item identity and priority must remain distinct, especially when several vertices have equal tentative distances.

The attractive compromise is local organization with global usefulness. A binary heap maintains only the heap order, yet every extract-min gives the next smallest key. Repeated extraction of the original example gives $2,3,4,5,7,8,9$, so a priority queue also supplies a sorting algorithm without storing a sorted array between extractions.

Binary search finds a target $x$ in a sorted array $A$ by inspecting the middle of the remaining candidate range. If the middle entry is smaller than $x$, every entry to its left is also too small; if larger, every entry to its right is too large. One comparison therefore rules out many entries. Equal entries are allowed; this version returns any matching index, without promising the first occurrence.

Use indices starting at zero and inclusive endpoints $L,R$. Initially $L=0$, $R=n-1$, where $n$ is the array length. While $L\le R$, chooseThe brackets denote the floor function. Compare $A_m$ with $x$: return $m$ on equality; set $L=m+1$ if $A_m<x$; otherwise set $R=m-1$. If $L>R$, report absence. The updates exclude the already inspected middle entry. This also handles an empty array, whose initial endpoints are $0,-1$. Sedgewick and Wayne specify a sorted array as input and return a matching index or $-1$ for absence.^[ref]

For a fully worked example, take the sorted arraySearch for $x=23$:

For $x=24$, the first two steps agree. Next $24>23$ retains only index $6$; inspecting $A_6=38$ sets $R=5$. Now $L=6>5=R$, so the answer is "absent" after four comparisons.

The loop invariant is: the array stays sorted, $0\le L\le R+1\le n$, and every index containing $x$ lies between $L$ and $R$. It holds initially. The sorted array property justifies each exclusion. Returning on equality gives a match; an empty candidate range implies absence. Crucially, this loop invariant allows $x$ to be absent from the beginning.

For a nonempty range of size $s=R-L+1$, an unsuccessful comparison leaves at most $\lfloor s/2\rfloor$ candidates. Thus sizes satisfy $s_k\le \lfloor n/2^k\rfloor$ after $k$ unsuccessful comparisons. This proves termination and, for $n\ge 1$, at most $\lfloor {\log }_{2}n\rfloor +1$ middle-entry comparisons. The final singleton still needs inspection: $n=1$ requires one comparison, not zero. For $n=15$, the bound is four. This is the halving argument behind logarithmic time complexity.^[ref]

A decision tree with $q$ binary tests has at most $2^q$ leaves. Distinguishing $n$ possible matching positions therefore requires $q\ge \lceil {\log }_{2}n\rceil$. This lower bound counts binary tests, whereas the bound above counts three-way comparisons.

Computer science studies how information can be represented and transformed by algorithms, and what those transformations can achieve. Its central questions connect mathematics to practical design: what answer should a procedure produce, why is it correct, and how much work does it require as its input grows? Computability theory asks which tasks can be solved at all; computational complexity theory asks what resources a solution needs.

The beauty is that choosing a representation can change what is feasible. Finding a name among a million entries sounds like a million checks. Store the entries in a sorted array, and binary search needs at most twenty middle-entry comparisons. The order makes each unsuccessful comparison eliminate a whole region of possibilities. A data structure supplies useful organization; an algorithm exploits it; time complexity explains the resulting savings.

Algorithm correctness covers every permitted input, including absent names and empty collections. Time complexity predicts scaling; statistical program profiling investigates a particular implementation.

A relation between abstract and concrete states used to prove data refinement. Establish it initially; show that each concrete operation simulates the specified abstract operation and restores the relation; show that returned observations agree. For a rank collection, $u[\mathrm{0..}n)=\mathrm{sort}(xs)$ and $n=\mathrm{length}(xs)$ justify constant-time indexed queries on a sorted array.

Implementation of an abstract state and operations using a more concrete representation, justified by a coupling invariant. For example, an insertion-history list may be implemented by a sorted array when clients observe only occurrence counts and order statistics. The observable behavior, rather than insertion order internally, must agree.

A data structure organizes stored information together with operations for accessing and changing it. Choosing a data structure means choosing which questions should be cheap to answer: an array supports access by numbered position, a hash table supports lookup by key, and a priority queue supports selecting an item by priority. The operations and their time complexity matter as much as the stored values.

Suppose three requests arrive as $(5,\mathrm{Ada}),(2,\mathrm{Bo}),(4,\mathrm{Cy})$, where the number is a priority and smaller numbers are more urgent. A FIFO queue removes Ada first because she arrived first. A minimum-oriented priority queue removes Bo first because $2$ is the least priority. An array can store the same three records in arrival order, but finding the least priority by scanning this representation takes three key inspections. A binary heap organizes these records so the least priority is immediately available. The information is the same; the representation changes the work needed to use it.

This is a useful design principle: preserve just enough organization for the operations the application needs. Maintaining a sorted array gives the whole order, but moving entries to insert a new key can be expensive. A binary heap keeps a weaker heap order that supports fast repeated selection without maintaining a sorted array. A good data structure makes an algorithm's next step easy.

For each candidate first index $i$ in a sorted array, use lower-bound search for $t-a(i)$ only in the suffix starting at $i+1$. A matching result is automatically at a different position. The outer loop invariant excludes all solutions whose smaller index precedes $i$; an unsuccessful suffix search extends this exclusion by one. Exhaustion proves absence of any pair. Searching all suffixes gives $O(N\log (N+1))$ running time and constant auxiliary space. Compute the complement in a sufficiently wide type to avoid integer overflow before comparison.

A divide-and-conquer algorithm divides a problem into smaller instances, solves them using recursion, and combines their answers. In merge sort, the division makes two contiguous halves, and the merge algorithm combines the resulting sorted arrays. The important design step is finding a combination rule cheaper than solving the whole problem afresh.

Halving the input is only one part of the design. The number of recursive calls and the work outside those calls determine whether the smaller instances actually save time. Divide-and-conquer combination cost keeps these quantities separate; the divide-and-conquer product ledger shows how an algebraic identity changes the number of required calls in Karatsuba multiplication.

For algorithm correctness, specify the meaning of each returned answer, prove the base cases, and show that combining correct smaller answers gives the required output. Induction then proves correctness, provided every recursive call progresses towards a base case. The combination rule must reconstruct everything the caller needs: two sorted halves alone are not a sorted array, and four digit blocks alone are not their integer product.

Find both the lower-bound search boundary $i$ and the upper-bound search boundary $j$ of a key $x$ in a sorted array. Every entry in $[i,j)$ is at least and at most $x$, so all are equal to $x$. Values immediately outside this interval, when present, are strictly smaller or strictly larger; the interval is consequently maximal. An absent key gives $i=j$ at its insertion position. Two binary searches give total time complexity $O(\log (N+1))$ under constant-cost comparison and indexed access.

The minimum convention for heap order requires every parent in a rooted tree to have priority no greater than each of its children in a rooted tree. The displayed formula uses the array representation of a binary heap. It permits equal priorities and does not require a sorted array; the maximum convention reverses the inequality.

A least-significant-digit radix sort processes numerical digits from smallest to largest place value. Fix integers $R\ge 2$ and $d\ge 1$, and take $n$ complete sorting records whose sort keys satisfy $0\le k<R^d$. Use exactly $d$ positions in positional notation with radix $R$, including leading zeros. At pass $j=0,\dots ,d-1$, apply a stable digit sort to the current array usingThe floor function selects the integer quotient, and the remainder selects the current numerical digit. Move the complete sorting record, including its associated data. There are exactly $d$ passes, so this procedure terminates even for an empty array. The radix sort suffix invariant supplies its algorithm correctness argument.

For an original input, let the letters identify the attached data:Here $R=10$, $d=3$, and leading zeros only align place values; $005$ represents the integer five. The exact pass ledger is:After the units pass, the numerical digits are $0,2,4,5,5,7,7,7$. The ties retain $C$ before $F$ and $B$ before $E$ before $G$. This array is not yet ordered by its whole integer sort keys: $314$ still precedes $305$. After the tens pass, the two-position suffixes are $05,05,14,17,27,27,40,42$. In particular, $217_E$ now precedes $027_B$: their tens numerical digits differ, so stable sorting does not require retaining their previous order. The hundreds pass produces the final sorted array, with all attached letters preserved.

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.

For a nondecreasing sorted array $a[\mathrm{0..}N)$ and target $x$, find the unique position $p\in [0,N]$ such that every earlier value is below $x$ and every later value is at least $x$. Equivalently, $p=\min (\{i\in [0,N):a(i)\ge x\}\cup \{N\})$. Uniqueness follows because, if $p<q$ both satisfied the partition, $a(p)$ would have to be both at least $x$ and below $x$. A half-open search interval maintains an excluded prefix of smaller values and an excluded suffix of greater-or-equal values. Allowing the sentinel $N$ handles an empty array or a target beyond its last entry.

Merge sort is a divide-and-conquer algorithm that sorts a finite array by splitting it into contiguous halves, sorting each half using recursion, and combining the two sorted arrays with the merge algorithm. An empty or one-entry array is returned immediately. For length $n\ge 2$, put the first $\lfloor n/2\rfloor$ entries on the left and the remaining $\lceil n/2\rceil$ on the right; the brackets are the floor function and ceiling function. Always choose the left head on equal keys to obtain stable sorting. This is the split, sort, combine structure taught in the MIT lecture notes.^[ref]

Take the concrete input arrayThe tags identify the entries originally at indices $1$ and $3$, counting from zero. Both keys are $2$; the tags are never compared. Reading downward in the figure follows the splits, then the returned sorted arrays. Arrows show dependencies; the level layout groups independent calls rather than giving their chronological execution order.

The first two halves are $(7,2_a,5,2_b)$ and $(9,1,4,3)$. Their pairs split into one-entry base cases. Applying the merge algorithm gives the following fully worked return levels; each number in the last column counts only comparisons between two available heads.

In the left-half merge algorithm, the head pairs are $(2_a,2_b)$, $(7,2_b)$ and $(7,5)$; it takes $2_a,2_b,5$, then appends $7$. In the final merge algorithm, the head pairs are $(2_a,1)$, $(2_a,3)$, $(2_b,3)$, $(5,3)$, $(5,4)$, $(5,9)$ and $(7,9)$. It takes $1,2_a,2_b,3,4,5,7$, then appends $9$. Thus this precise version makes $4+6+7=17$ head comparisons and, ignoring identity tags, returns $(1,2,2,3,4,5,7,9)$.

The elegance of merge sort is that it creates exactly the structure its next step needs: two smaller sorted arrays make the larger ordering inexpensive. Once the whole array is sorted, equal keys are adjacent and binary search can serve repeated queries. Stable sorting also retains information that the keys alone do not express. If the left-half merge algorithm instead takes the right head on the $2_a=2_b$ tie, it returns $(2_b,2_a,5,7)$; the keys are sorted but stable sorting has failed.

For time complexity, assume each key comparison, entry access and entry copy has constant cost. The merge algorithm processes $n$ entries in $O(n)$ time. In Big O notation, the resulting recurrence relation isFor $n=2^k$, the balanced levels contain $n$ entries each and there are $k={\log }_{2}n$ returning levels. Each costs $O(n)$, so the worst-case time complexity is $O(n\log n)$. For arbitrary $n$, there are at most $\lceil {\log }_{2}n\rceil$ returning levels, each processing at most $n$ entries, giving the same bound. The worst-case number of head comparisons is also $O(n\log n)$. Here ${\log }_2$ is the base-two logarithm. The MIT notes give this level-by-level analysis for merge sort.^[ref]

The conventional array implementation uses a reusable buffer of $n$ entries for the merge algorithm, together with $O(\log n)$ pending calls for recursion. Its auxiliary space complexity is therefore $O(n)$, beyond the original array. This bound describes that implementation. A linked list permits a merge algorithm that reconnects existing nodes; its storage accounting differs from copying array entries into a buffer.

For a short algorithm correctness outline, the empty and one-entry base cases are sorted. Assuming recursion correctly sorts both shorter halves, the merge algorithm returns all their entries in order. Equal keys within a half keep their relative order by the same argument applied to the smaller call; across halves, every left entry originally preceded every right entry, so taking left first preserves stable sorting. Both half-lengths decrease for $n\ge 2$, establishing termination.

Use two array indices, advancing only the smaller current entry. Here and in Questions 1–4, code is structured Oberon-style pseudocode: RETURN exits a procedure, Some(x) and None distinguish success and absence, and AND short-circuits from left to right. Arithmetic is exact where the source asks us to ignore integer overflow.Let $z$ be the smallest common value, and let $a[p]=b[q]=z$. Existence implies $N,M>0$. A useful loop invariant is $0\le i\le p<N$, $0\le j\le q<M$, with no common value among the discarded prefixes $a[\mathrm{0..}i)$ and $b[\mathrm{0..}j)$. Initially the prefixes are empty. If $a[i]<b[j]$, then $a[i]$ cannot equal any entry of $b[j..M)$ because that sorted array is increasing; it cannot be a common value in the discarded prefix either. Moreover $i=p$ would imply $z=a[i]<b[j]\le z$, a contradiction. Thus $i<p$ and incrementing $i$ is safe. The other branch is symmetric.

Every guard and return therefore uses valid array indices, even without explicit bounds tests. The loop variant $(p-i)+(q-j)$ decreases on each iteration. At exit the equal entries form a common value no larger than $z$, hence equal $z$. There are at most $N+M-2$ increments and constant work per increment. The procedure returns the smallest common value in $O(N+M)$ time and $O(1)$ auxiliary space.

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.

For an ascending sorted array, maintain a candidate interval $[\ell ,r]$ initially containing every index. Compare the target with the middle entry at $m=\lfloor (\ell +r)/2\rfloor$. Equality returns $m$; if the target is smaller, replace $r$ by $m-1$; if larger, replace $\ell$ by $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 $\lfloor {\log }_{2}n\rfloor +1$ comparisons suffice for $n\ge 1$. Each iteration uses constant work on a random-access array. Thus binary search takes $O(\log (n+1))$ running time, conventionally written $O(\log n)$ for nontrivial input sizes. Empty input is handled in constant time.

Assume ascending sorted arrays; descending storage can be accessed in reverse index order without copying. Among $2n$ 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)\le i\le \min (n,k)$. Write $A_L=A[i]$, $A_R=A[i+1]$, and similarly $B_L,B_R$ at $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$:

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(\log (n+1))$ running time and $O(1)$ auxiliary space. This is a two-sorted-array order statistic without constructing the merged array.