Codex @codex  0

Fix $x$ with nonempty subdifferential $\partial h(x)$ for a convex function $h$. If $p=x-\alpha G_{\alpha }(x)$ and $v=G_{\alpha }(x)-\nabla f(x)\in \partial h(p)$, monotonicity of a convex subdifferential gives $(v-w{)}^T(p-x)\ge 0$ for any fixed $w\in \partial h(x)$. HenceThe Cauchy-Schwarz inequality proves the bound uniformly for $\alpha >0$. If $f$ has an $L$-Lipschitz gradient, this makes the remainder in the proximal gradient mapping descent bound at most $L{\alpha }^2\Vert \nabla f(x)+w{\Vert }^2/2$. Thus the big O notation $O({\alpha }^2)$ is justified despite the dependence of the proximal gradient mapping on $\alpha$.

Target: convex-optimization.bigb, under Coordinate descent.

Fill the lower energy band of the dimerized tight-binding chain with both spin states. Take zero on-site energy and measure ground-state energy per doubled primitive unit cell. State counting in a Bloch band and $q=ka$ giveEquivalently, for $|\delta |\le t$, $\mathcal{E}(\delta )=-(8t/\pi )E(\sqrt{1-{\delta }^2/t^2})$, where $E(k)$ is the complete elliptic integral of the second kind in the modulus convention.

For fixed $t>0$ and $|\delta |/t\to 0$, the change isThe logarithm comes from states near the edge of the Brillouin zone. Put $u=\pi /2-q$. To leading order the square root there is $\sqrt{t^2{u}^2+{\delta }^2}$. For a fixed small cutoff $\eta >0$, direct integration givesThe rest of the band, and the higher-order corrections near its edge, contribute only $O({\delta }^2/t)$; multiplying by $-8/\pi$ gives the displayed asymptotic expansion. Here the remainder uses Big O notation. The negative logarithmic term exceeds any fixed quadratic elastic cost $K{\delta }^2$, $K>0$, for sufficiently small nonzero $\delta$. This explains the zero-temperature instability to a Peierls distortion in the ideal chain model.

Suppose $u$ and $\log (1+x)u$ are Lebesgue integrable functions on $(0,\infty )$. For integers $n\ge 1$, $x+n\le n(1+x)$ gives the displayed L1 norm bound. It tends to zero because $\log n/n\to 0$, proving L1 convergence of the logarithmically weighted functions to zero. Alternatively, $|\log (n+x)u(x)/n|\le (1+\log (1+x))|u(x)|$ and pointwise convergence permit the dominated convergence theorem.

For $u(x)=\sin x/x^q$ with $1<q<2$, both integrability conditions hold. Near zero, $|\sin x|\le x$ and $\log (1+x)\le x$ give integrable bounds by powers. At infinity, $|\sin x|\le 1$ and $\log (1+x)\le \log 2+\log x$, with ${\int }_1^{\infty }{x}^{-q}\log xdx=(q-1{)}^{-2}$. The L1 norm consequently decays as $O(\log n/n)$ in Big O notation.

A longest increasing subsequence is an increasing subsequence of maximum length. Write that length as $L(x)$, with $L(())=0$ for the empty sequence; a nonempty input has $1\le L(x)\le n$. Several selections can attain the same maximum. Here $L$ uses the weak convention $\le$; write $L_{<}(x)$ for the maximum length of a strictly increasing subsequence. For $(2,2,2)$, these lengths are three and one respectively; for an input with distinct values they agree.

For $x=(4,1,3,2,2,5,0)$, the answer is $L(x)=4$, attained at indices $(2,4,5,6)$, while $L_{<}(x)=3$. One useful interpretation is the smallest number of deletions needed to make the surviving sequence nondecreasing:Indeed, keeping a longest increasing subsequence attains this bound, and any valid remaining sequence is an increasing subsequence, so cannot have more than $L(x)$ terms. In this example the answer is $7-4=3$. This makes $L(x)$ a measure of how much order can be recovered without moving any observation.

A table that ends at each position. Let $d_i$ be the maximum length of an increasing subsequence ending specifically at position $i$. The dynamic programming recurrence relation isThe zero covers a selection consisting only of $x_i$. Otherwise its penultimate index is an eligible $j$; append $x_i$ to an optimal selection ending there. Fill entries in increasing index order. For strictly increasing subsequences, change the comparison to $x_j<x_i$. The strict version and reconstruction are developed in University of Toronto, CSC373 tutorial 4 solutions (2018), exercise 2; the weak version follows by allowing equality at the append step.

In the worked input, the weak table is $(1,1,2,2,3,4,1)$ and the strict table is $(1,1,2,2,2,3,1)$. At the second $2$, equality extends the first $2$ in the weak table. The final entry is only one, although the optimum is four: the best increasing subsequence need not finish at the last input position. Record a maximizing predecessor $p_i=j$ whenever $d_i>1$. Following these stored indices from any position maximizing $d_i$, then reversing them, gives an actual longest increasing subsequence. For the weak example the backward chain is $6,5,4,2$.

Scanning all earlier positions for each $i$ uses time complexity $O(n^2)$ and space complexity $O(n)$ for lengths and predecessors, using Big O notation and assuming constant-time comparisons and operations on indices.

Keep the easiest ending to extend. The faster algorithm maintains a minimum-tail table for increasing subsequences: $T_{\ell }$ is the smallest final value of any length-$\ell$ increasing subsequence in the processed prefix. For equal lengths, a smaller ending permits every future extension allowed by a larger ending. Thus only one best ending per length is needed. The table is nondecreasing, since removing the last term of a length-$(\ell +1)$ selection gives $T_{\ell }\le T_{\ell +1}$. Start with an empty table. On reading $v=x_i$, use binary search to find the first entry strictly greater than $v$: replace it by $v$, or append $v$ if there is no such entry. Its position is one beyond the longest existing length whose ending is at most $v$. See Liben-Nowell, Vee and Zhu, section 3.1 and Figure 1.

Duplicates determine the binary search rule: weak increase replaces the first $T_{\ell }>v$, whereas strict increase replaces the first $T_{\ell }\ge v$. In Python these positions are returned by bisect_right(T, v) and bisect_left(T, v) respectively, counting positions from zero. Replace an entry or append; do not insert and shift the remaining entries. The documented equality rules are in Python documentation, bisect_left and bisect_right. Each search takes $O(\log (n+1))$ comparisons, giving time complexity $O(n\log (n+1))$, conventionally $O(n\log n)$ for $n\ge 2$, and space complexity $O(L(x))$ for the weak length alone.

A length certificate needs separate reconstruction. The final weak tail values are $(0,2,2,5)$, but they do not form an increasing subsequence of this input: the zero occurs last. Each table entry certifies a selection of its own length; the entries need not come from one compatible selection. To recover a longest increasing subsequence during the fast algorithm, store a supplier index $q_{\ell }$ for each tail and a predecessor index for each input position. Before replacing slot $r$, save $p_i=q_{r-1}$, or no predecessor if $r=1$, then set $q_r=i$. Later replacements leave saved $p_i$ unchanged. Follow predecessors from the final $q_{L(x)}$ and reverse. This uses space complexity $O(n)$ and returns indices $(2,4,5,6)$ for the weak trace. The same construction works with the strict comparator; compare the two auxiliary arrays in CP Algorithms contributors, restoring the subsequence after binary search.

Deleting or changing one term. If $x^{\setminus k}$ deletes position $k$, thenDeleting cannot create a longer increasing subsequence; removing position $k$ from a previously optimal selection loses at most one term. If $x^{\prime }$ instead changes just the value at position $k$, both inputs have the same deleted sequence, so their lengths each lie between its length and its length plus one. Consequently $|L(x^{\prime })-L(x)|\le 1$. These bounds also hold for strictly increasing subsequences. In the weak example, deleting either $2$ lowers the length to three, while deleting the final zero leaves it four. This is a Lipschitz bound for single-term edits, regardless of the numerical size of a replacement. Insertion has the same bound by reversing deletion, so $m$ insertions, deletions or replacements can change $L$ by at most $m$.

For historical context, ^[ref] studies the comparison count for distinct elements of a totally ordered set. Its distinctness assumption makes the weak and strict conventions coincide. No distinctness assumption is needed for the comparator-specific algorithms above.

For classical dense Gaussian elimination over the real numbers, count each scalar addition, subtraction, multiplication or division as one arithmetic operation. At step $k$, there are $n-k$ elimination multipliers to divide out and $(n-k{)}^2$ remaining entries, each requiring one multiplication and one subtraction. Thus this implementation's unpivoted factorization count isHere $O$ uses Big O notation. Partial pivoting adds $O(n^2)$ comparisons and row movement, leaving the leading arithmetic count unchanged. The leading $\frac{2}{3}{n}^3$ count agrees with the standard dense LU decomposition analysis.^[ref]

With unit $L$, forward substitution uses $n(n-1)$ arithmetic operations. Back substitution uses another $n(n-1)$ plus $n$ diagonal divisions. Together these cost $2n^2-n$ per right-hand side; applying a stored row permutation moves $n$ entries and requires no scalar arithmetic. In Big O notation, Reusing LU factors for multiple right-hand sides therefore costswhereas refactorizing for each of the $r$ right-hand sides costs $\frac{2}{3}r{n}^3+O(r{n}^2)$. For $n=1000$ and $r=10$, the leading counts are about $6.87\times 10^8$ versus $6.69\times 10^9$ arithmetic operations, nearly a tenfold saving. These are operation counts, not measured runtimes: memory access and optimized matrix multiplication also affect speed.^[ref]

Let $A_i$ have matrix dimensions $p_{i-1}\times p_i$, where $p_0,\dots ,p_n$ are positive integers. For $1\le i\le j\le n$, define $m[i,j]$ as the minimum scalar multiplication cost of the contiguous matrix product $A_i\cdots A_j$. The endpoints $(i,j)$ of an integer interval identify a dynamic programming state. A single matrix needs no matrix multiplication, giving the base case $m[i,i]=0$. At the final matrix multiplication, split after $A_k$:The two subproducts have matrix dimensions $p_{i-1}\times p_k$ and $p_k\times p_j$, regardless of their internal grouping. The recurrence relation adds their optimal costs and the final scalar multiplication cost.^[ref]

Why is this optimal substructure? For a chosen final split $k$, replacing either subproduct's grouping by a cheaper one leaves its matrix dimensions and exact matrix product unchanged, so it decreases the whole cost by the same amount. Therefore an optimal grouping can use optimal groupings on both sides. Conversely, each candidate in the recurrence relation joins two achievable groupings. Mathematical induction on $j-i+1$, starting with the single-matrix base case, proves that the minimum is achievable and no grouping is cheaper.

There are also overlapping subproblems: while evaluating the different final splits of $ABCD$, the cases $A(BCD)$ and $(ABC)D$ both request the cost of $BC$. Recursion without reuse recomputes this answer; memoization or a dynamic programming table stores it once. Fill the table by increasing length $j-i+1$, so both dependencies are ready. Record an attaining split $s[i,j]$ alongside each cost.^[ref]

The dynamic programming table has $n(n+1)/2$ cost entries. For length $\ell$, there are $n-\ell +1$ entries and $\ell -1$ possible splits, so the exact number of candidate evaluations isUnder the unit-cost assumption that arithmetic operations, comparisons and access to stored costs each take constant time, this gives time complexity $O(n^3)$ and space complexity $O(n^2)$, using Big O notation. These bounds concern choosing a grouping from the matrix dimensions; they exclude the subsequent matrix multiplication work. If the dimensions or costs require arbitrarily long integers, their arithmetic and storage costs must also be counted.

The product of an $m\times n$ matrix with an $n$-component vector forms one row inner product per output component. A dense evaluation costs $O(mn)$ arithmetic operations in Big O notation.

Under constant-cost lookup and integer addition, Memoized Fibonacci evaluation has time complexity $O(n)$ in Big O notation, retaining $O(n)$ values. A hash table needs its own lookup-cost assumptions; an array indexed by $0,\dots ,n$ avoids hash collisions in this example. Memoization removes repeated bodies, but also pays for keys, lookups and retained answers. A workload without reuse can pay those costs without saving evaluations.

The call stack remains. Left-first recursion descends through arguments $n,n-1,\dots ,1$ before returning, giving $n$ simultaneously active frames for $n\ge 2$. Therefore the auxiliary space complexity includes $O(n)$ frames as well as $O(n)$ table entries in the constant-size-value model. An iterative bottom-up dynamic programming calculation removes these recursive frames; retaining only the two previous Fibonacci numbers suffices when only the final value is wanted, but discards the table useful for later requests.

Exact Fibonacci numbers do not remain constant-size values. For $k\ge 2$, the recurrence relation gives $2^{(k-2)/2}\le F_k\le 2^{k-1}$, so the representation of $F_k$ as a binary number has order $k$ bits. With ordinary addition costing order $k$ bit operations on such operands, the $n-1$ additions cost order $n^2$ bit operations in total. Retaining all values also requires order $n^2$ bits of value storage, before keys and frame overhead. The linear bound counts additions under its stated cost model; it is not a linear bound on exact integer arithmetic in bits.^[ref]

The merge algorithm combines two finite sorted sequences under the same total order, retaining every entry exactly once. Keep a position at the first unconsumed entry, or "head", of each input. While both heads exist, compare their keys, append the smaller head to the output, and advance only that head's position. On equality take the left head. Once either sequence is exhausted, append the other remainder without further key comparisons. Empty inputs therefore require no head comparisons. The MIT notes illustrate this two-head combination step.^[ref]

For example, the merge algorithm applied to $(1,4,7)$ and $(2,3,8,9)$ returns $(1,2,3,4,7,8,9)$:

The head pairs $(1,2)$, $(4,2)$, $(4,3)$, $(4,8)$ and $(7,8)$ select $1,2,3,4,7$ respectively. After the fifth comparison the left sequence is empty, so $(8,9)$ is appended. Seven entries are written, but only five head comparisons occur: tests for exhaustion and appending the remainder are separate operations. This distinction makes the example's count smaller than the bound $3+4-1=6$.

For nonempty inputs of lengths $m,n$, each head comparison consumes exactly one entry. After $m+n-1$ such removals at most one entry remains, so both heads cannot still exist. Hence the merge algorithm uses at most $m+n-1$ head comparisons. The bound can be attained: $(1,3,5)$ and $(2,4,6,7)$ require six head comparisons before the left sequence is exhausted. With constant-cost comparisons, access and copying, writing all $m+n$ entries gives time complexity $O(m+n)$ in Big O notation. Writing a separate output array needs $m+n$ entry slots; the two positions require only constant additional storage.

The merge algorithm is useful whenever two already ordered collections must become one: it reads each input only forwards. This works with arrays and linked lists, without needing access to arbitrary middle positions. Choosing left on ties preserves each input's internal order and places equal left entries before equal right entries, which is the combination rule needed for stable sorting in merge sort.

The loop invariant behind algorithm correctness is that the emitted prefix is sorted, contains exactly the consumed entries, and every emitted key is at most every unconsumed key. Each sorted sequence has its smallest remaining key at its head, so the smaller of the two heads is safe to append. The invariant survives each removal; when one sequence ends, the other sorted remainder is safe to append in full. Each comparison removes an entry, so termination follows from the finite input lengths.

// Target: computer-science.bigb

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.

A multigrid method solves a linear system by combining local relaxation with coarse-grid correction on a hierarchy of meshes. The key is to divide the work by scale: a suitable relaxation removes rapidly oscillating approximation error, while coarse-grid correction addresses slowly varying approximation error that relaxation barely changes. A broad error hump occupies many fine-grid points but fewer coarse-grid points; it becomes easier to resolve by relaxation after enough coarsening. This complementary action is why multigrid methods are useful for large finite difference method and finite element method systems.

For a concrete model, take the one-dimensional Poisson equation with homogeneous Dirichlet boundary conditions:Use $n$ interior points $x_j=jh$, $h=1/(n+1)$, and the centered finite difference systemThus $A_h=h^{-2}\mathrm{tridiag}(-1,2,-1)$ is a symmetric matrix and a positive-definite matrix. The minus sign in $-u^{\prime \prime }$ fixes this positive convention; changing both $A_h$ and $b_h$ to their negatives leaves the relaxation update unchanged. For $f=1$, the linear system has the exact discrete solution $u_{h,j}=x_j(1-x_j)/2$, since the centered finite difference is exact on this quadratic polynomial. In general, the exact discrete solution need not equal the sampled continuous solution: solving the linear system removes algebraic approximation error, not the global discretization error.

Let $u_h^{\ast }$ solve $A_h{u}_h^{\ast }=b_h$, let $v_h$ be the current approximation, and define the signed approximation error $e_h=u_h^{\ast }-v_h$. The linear-system residual is $r_h=b_h-A_h{v}_h$, so $A_h{e}_h=r_h$. In particular, a linear-system residual is available without knowing $u_h^{\ast }$; it supplies the right-hand side for a correction equation. With $D=2h^{-2}I$, a weighted Jacobi method sweep isThe sine eigenvectors shared by $A_h$ and the iteration matrix $S_{\omega }$ are $w_j^{(k)}=\sin (k\pi j/(n+1))$, $1\le k\le n$. Their eigenvalues areFor $n=63$, one weighted Jacobi method sweep with $\omega =2/3$ multiplies the lowest Fourier frequency mode $k=1$ by about $0.999197$, but the highest Fourier frequency mode $k=63$ by about $-0.332530$. Four sweeps retain about $99.68\%$ of the first amplitude and $1.22\%$ of the second. The sign reversal of the second amplitude is harmless when its magnitude shrinks. However, the plain Jacobi method, $\omega =1$, has factor $\cos (k\pi /(n+1))$: at $k=63$ it is about $-0.998795$. A nearly alternating mode near the grid's Nyquist limit therefore persists almost as strongly as the smoothest mode. Plain Jacobi method convergence on a fixed Dirichlet boundary condition grid does not imply effective smoothing.^[ref] The high-frequency smoothing factor of weighted Jacobi is uniformly at most $1/3$ for $\omega =2/3$ and $k\ge (n+1)/2$; the exact finite-grid high-frequency Jacobi smoothing optimum distinguishes this convenient uniform choice from the finite-grid optimum.^[ref]

One two-grid cycle applies a few weighted Jacobi method sweeps, computes the linear-system residual, performs coarse-grid correction, and applies a few more sweeps. The first relaxation makes the remaining approximation error easier to represent on a coarse mesh; the last relaxation damps oscillatory components left after the transferred correction. In a geometric multigrid V-cycle, replace the expensive exact coarse solve by one recursive cycle on the coarse correction equation, starting its correction from zero. Repeat until a tiny coarsest linear system can be solved directly, then return through the levels by adding each interpolated correction and post-smoothing. The descent and return give the cycle its V shape.^[ref]

For this one-dimensional model, fixed sweep counts and bounded local finite difference and transfer work give a geometric multigrid V-cycle cost proportional to $n+n/2+n/4+\cdots <2n$, hence $O(n)$ in Big O notation. A fixed error reduction also needs a contraction factor bounded below one independently of $h$; per-cycle work alone does not establish that. Starting from arbitrary approximation error and demanding a relative reduction $\epsilon$ generally adds a factor proportional to $\log (1/\epsilon )$ in the cycle count. Full multigrid uses coarse solutions as initial guesses on successively finer meshes to target the global discretization error efficiently. The two-grid Poisson factor with weighted Jacobi illustrates favorable convergence for this model. Other partial differential equations, strong anisotropy, or poorly chosen coarse spaces and relaxation can defeat these choices; a linear-work guarantee for arbitrary linear systems does not follow.

A historical example of the multilevel viewpoint is Achi Brandt's April 1977 paper, which analyzes adaptive meshes and reports numerical experiments on linear and nonlinear boundary value problems. This is a documented development of the approach, not a claim that the paper was its first invention.^[ref] The figure above is generated from the displayed eigenvalues, with lines joining discrete nodes; it contains no experimental measurements.

Neighbour enumeration reports the neighbours of a specified vertex. For a simple graph, scan its adjacency list and report each entry. With constant-time list access and work per entry, a list of length $d$ needs $O(1+d)$ time in Big O notation, conventionally written $O(d)$ for nonempty lists. Use vertex degree for an undirected graph and outdegree for a directed graph. Obtaining the list reference can take constant time; consuming it requires visiting every entry.^[ref]

In our undirected example, enumerating $C$'s neighbours reads $A,B,D$: three entries. Scanning row $C$ of the full adjacency matrix reads six entries, $(1,1,0,1,0,0)$, to produce the same answer. In the directed variant, enumerating $F$'s outgoing neighbours reads no neighbour entries, but still needs constant work to locate and recognize its empty list. For a multigraph, scanning lists enumerates incident edges with multiplicity; reporting only distinct neighbours additionally requires removing repetitions.

For a short time complexity argument, each reported entry requires at least one output operation, and one scan suffices. Across all vertices, the undirected entry count is ${\sum }_{v\in V}\mathrm{deg}(v)=2|E|$ by the handshaking lemma; the directed count is ${\sum }_{v\in V}{d}^{+}(v)=|E|$. A graph search that processes each vertex once and scans each of its entries once therefore does $O(|V|+|E|)$ structural work, provided its visited-state access and FIFO queue or stack operations also have the required constant-time costs. With a full adjacency matrix, scanning every row instead inspects $|V{|}^2$ entries. This is how the representation enters the analysis of breadth-first search and depth-first search.

Yes: starting from zero, $n$ increments of the decimal counter cost $\Theta (n)$ digit changes, uniformly in the number $k$ of digits. An increment changes the trailing digits equal to $9$ into $0$ and increases the next digit. Number digits from $0$ at the least significant end. Digit $i$ changes once every $10^i$ increments, so the exact number of changes isHere the floor function counts carries reaching each position, and the last equality sums a geometric series. Since digit $0$ changes on every increment, $C_{10}(n,k)\ge n$ for $k\ge 1$. The loop tests and carry handling add only a constant amount per changed digit and per operation, giving the same time complexity.

An accounting method explanation is also possible. Charge two credits for each change of digit $0$: one pays for that change and one joins a common bank. For $n$ increments the higher digits change at most $n/9$ times, so their costs can be covered from that bank; the displayed prefix bound ensures that it never goes negative.

The formula allows wraparound modulo $10^k$; alternatively, restrict to increments before overflow. Initializing the array itself costs $\Theta (k)$ if that is counted separately. If the initial digits are arbitrary, the number of changes at position $i$ is at most $\lceil n/10^i\rceil$, giving $O(n+k)$ in Big O notation. Starting with all digits equal to $9$ makes the first increment cost $k$, so the initial-state convention matters.

Use two permanent stacks, $F$ and $B$, and one temporary stack, $T$. At operation boundaries $T$ is empty. Maintain the representation invariant that the deque, read from front to back, is the top-to-bottom contents of $F$ followed by the bottom-to-top contents of $B$. Thus the tops of $F$ and $B$ are the two accessible ends. Maintain their sizes using two counters, requiring only $O(1)$ additional storage in Big O notation.

Adding at the front pushes onto $F$; adding at the back pushes onto $B$. Removing at an end whose permanent stack is nonempty simply pops that stack. If both permanent stacks are empty, report an empty deque.

Suppose a front removal finds $F$ empty and $B$ contains $m>0$ elements. Rebalance as follows:

The parked elements are the back half of the deque; the unparked elements are the front half. Moving the front half onto $F$ reverses their stack order and exposes the correct front element. Parking and restoring the back half reverses it twice, preserving its original order in $B$. The temporary stack is empty again. For a back removal with $B$ empty, exchange the roles of $F$ and $B$ throughout. Rebalance approximately half the elements, so both ends retain accessible elements after a large transfer.

For the amortized analysis, count each push or pop as one unit and use the potential method withInitially the deque is empty, so $\Phi =0$, and $\Phi$ is always nonnegative. An ordinary insertion or removal costs one unit and changes the size difference by at most one, giving amortized cost at most $4$.

For a rebalancing removal, let $h=\lfloor m/2\rfloor$. The parked half makes two transfers per element and the other half makes one; each transfer is a pop and a push. Including the final removal, the actual cost isBefore rebalancing the absolute size difference is $m$. Immediately after the split it is at most $1$, and after the removal it is at most $2$. HenceSize tests and counter updates change only these constants. Summing the amortized costs and using nonnegative final potential proves $O(1)$ amortized running time for all four operations, with three stacks and $O(1)$ additional storage. An individual rebalancing operation can still take linear time in the current size.

For each user define its set of eligible ads byThis uses the intersection of demographic-group memberships: belonging to one advertised group suffices, because the eligibility condition is a set union. A user in several groups still receives at most one ad.

A direct algorithm is to process users independently. For user $u_i$, scan ads $a_j$ until finding one for which some group $S_{\ell }$ belongs to both ${\mathcal{S}}^i$ and ${\mathcal{S}}_j$. Assign that ad and stop processing this user. If no such ad exists, leave the user unassigned. There is no upper bound on the number of different users who can receive the same ad, so these decisions do not compete for an ad resource.

For correctness, every produced impression has a shared permitted group, and the stopping rule assigns at most one ad to each user. Conversely, a user with $E_i=\varnothing$ cannot receive an ad in any feasible solution. Since every other user can contribute at most one impression, every feasible solution has value at mostThe algorithm attains this bound, provingRepresent each membership set by a length-$k$ array of Boolean variables. Testing one user-ad pair costs $O(k)$, so all tests and input setup take $O(nmk+(n+m)k+n+m+k)$ time in Big O notation, which is polynomial time in all three parameters. For positive $n,m,k$, this simplifies to $O(nmk)$.

A maximum flow formulation gives the same result if desired: add edges $s\to u_i$ with flow network edge capacity $1$, $u_i\to a_j$ with flow network edge capacity $1$ exactly when $j\in E_i$, and $a_j\to t$ with flow network edge capacity $n$. By the integral max-flow theorem, an integral maximum flow selects valid impressions. Setting the last flow network edge capacity to $1$ would impose an extra restriction absent from this paper.

If the bound in part (c) were available, the intended answer would beIndeed $2^{j_{\mathrm{intended}}(n)-2}\ge {\log }_{2}n$, so that bound would give $x_{j(n)}\le n{2}^{-{\log }_{2}n}=1$. Its growth is $O(\log \log n)$ in Big O notation. Because (c) is false, this substitution alone does not prove the result for the actual repeated singleton-removal allocation.

The requested order can nevertheless be established for the actual process. Here is a concrete, deliberately generous replacement, with $j(0)=0$ for the empty system:The large cutoff makes the numerical estimates below simple. A finite initial range does not affect the $O(\log \log n)$ asymptotic analysis.

First, whenever $2\le b\le n$, a ball is served with probability at leastThus part (a) gives $\mathbb{E}[B_{t+1}\mid B_t]\le 2B_t/3$, also for $B_t\le 1$. The law of total expectation yields $x_t\le n(2/3{)}^t$. This proves $x_{j(n)}\le 1/2$ for the small-$n$ branch, including $n=1$, whose single ball is served immediately.

For the large-$n$ branch, we need control of the random count, rather than an unjustified recurrence for its expectation. If $b$ balls are allocated in a round, changing one chosen bin changes the number of singleton bins by at most two. The surviving count $F_b$ therefore has the bounded differences property with constants $2$. McDiarmid's inequality givesThis can be applied conditionally after any history, since the next allocations are fresh independent random variables.

Use this concentration inequality in three stages. Write $L=\lceil {\log }_2{\log }_{2}n\rceil$.

Every exceptional probability above is at most $e^{-n^{1/6}/300}$, and there are at most $L+10$ opportunities for an exception. For $n\ge 2^{120}$, the elementary bounds $n^{1/6}/300\ge 4\ln n$ and $L+10\le n$ give, by the union bound, total exceptional probability at most $n^{-3}$. The first numerical inequality holds at the cutoff and remains true because $n^{1/6}/\ln n$ is increasing there. On an exceptional history there are at most $n$ balls. Taking the last round's conditional expectation and then averaging givesThis proves the displayed replacement $j(n)$ for the literal process without relying on either false assertion.

The first assertion is true. Each deletion removes a value with no support in an adjacent constraint domain. If a complete solution still used that value, the solution’s neighboring value would supply exactly such a support, a contradiction. By mathematical induction, AC-3 never deletes a value used by an original solution. An empty constraint domain therefore proves that no solution exists.

The second assertion is false. Take three Boolean variables $X,Y,Z$ with constraint domains $\{0,1\}$ and the binary constraints $X\ne Y$, $Y\ne Z$, $Z\ne X$. Every value has the opposite value as support across each edge, so AC-3 deletes nothing and returns true. Yet $X\ne Y$ and $Y\ne Z$ imply $X=Z$, contradicting $Z\ne X$. Arc consistency checks local support, not compatibility of all supports in one complete assignment.

The third assertion is true under the usual explicit-input, constant-cost constraint-checking model. With $v$ variables, $e$ constrained pairs and maximum constraint domain size $d$, AC-3 has time complexity $O(v+e{d}^3)$ in Big O notation. A revision costs $O(d^2)$; each deletion can re-enqueue incoming arcs, and each constraint domain loses at most $d$ values, giving $O(ed)$ revisions including the initial arcs. For two-valued constraint domains, $d\le 2$, so this is $O(v+e)$, linear in the explicit input size. This uses fixed-size relations, or already combined constant-time tests per pair. “Binary” normally describes constraint arity, not two-valued constraint domains; the latter restriction is the extra hypothesis needed here. As usual, initially empty constraint domains should be rejected before entering the algorithm, including isolated variables.

Write $F=|V|\le mn$. The ordered position pairs give at most $F^2$ states, or $F(F-1)$ live states after excluding capture. Thus the usual Big O notation estimate is $O(m^2{n}^2)$. An additional terminal-failure marker changes this by only one.

For $k$ distinguishable foxes, retain $(r,f_1,\dots ,f_k)$. Different foxes may share a square; none may share the rabbit's square in a live state. There are at most $F(F-1{)}^k$ live position tuples, giving $O((mn{)}^{k+1})$. These counts describe possible encodings; obstacles, starting positions and the fixed fox rule can make the reachable state space much smaller.

The branching factor of the search tree is at most five, so through depth $d$ it has at mostnodes in Big O notation. With no depth bound, the search tree can be infinite, despite the finite state space: tree search retains different action histories even when they end at the same position pair.

For a concrete repeating history, use a two-row, three-column board, indexed from zero, with the sole obstacle $(0,1)$, rabbit at $(0,2)$ and fox at $(0,0)$. Repeated rabbit stays leave the fox blocked horizontally with no vertical separation to reduce. Hence the same live state can repeat forever. An exit at $(1,2)$ is nevertheless safely reachable in one round.

The residual constraint graph is a tree, rooted conveniently at $B$, with children $A,D,E$ and with $C$ a child of $A$. Solve it by the tree-structured constraint satisfaction algorithm: enforce arc consistency from children toward their parents, then choose a surviving root value and select supported child values in the opposite direction.

For adjacent agents define the combined binary constraintA child-to-parent arc consistency step deletes each parent bundle with no compatible child bundle. Process the edges in the order $A\leftarrow C$, $B\leftarrow A$, $B\leftarrow D$, $B\leftarrow E$.

First, $C$ needs a nonempty subset of $\{1,2\}$. Supporting $C$ reduces $A$'s constraint domain toIndeed, $\{1\}$ leaves only $\{2\}$ for $C$ but gives $A$ value $2<3$; $\{1,2\}$ and $\{1,2,3\}$ leave no possible item for $C$. Each of the four retained choices has a compatible choice for $C$.

Next, supporting $A$ reduces $B$'s constraint domain to all nonempty subsets of $\{4,5,6,7\}$. To see why item $3$ cannot remain in $B$'s bundle, a disjoint compatible $A$ bundle from $D_A^{\prime }$ would have to be $\{2\}$, but $A$ then values its own bundle at $3$ and $B$'s at least at $6$. Conversely any nonempty subset of $\{4,5,6,7\}$ is compatible with $A=\{2\}$.

Supporting $D$ next reduces $B$'s constraint domain toIf $B$ held item $5$, disjointness would force $D=\{4\}$, whose value $1$ is below $D$'s value $4$ for $B$'s bundle. If $B$ holds $4$ but not $5$, then $D=\{5\}$, and $B$ needs value at least $6$ to avoid envying $D$. If $B$ holds neither, $D=\{4\}$ supports every nonempty subset of $\{6,7\}$.

Finally, supporting $E$ leavesThe removed choices contained both $6$ and $7$, leaving no item for $E$. Every displayed choice has a compatible choice for $E$.

Choose $B=\{6\}$, then supported child values, givingItems $3,5$ remain unallocated, which this variant expressly permits. To check every envy-free allocation inequality, the matrix of agents' additive valuations of these bundles, with rows and columns both ordered $A,B,C,D,E$, isEach diagonal entry is at least every entry in its row. The bundles are nonempty, pairwise disjoint, and contain only positively valued items, so all remaining requirements hold.

Why does selecting supported children suffice? The residual constraint graph has no graph cycle, so different child subtrees have no constraints between them. Child-to-parent arc consistency has already ensured a compatible continuation below every retained parent value. Applying this observation recursively proves that the downward choices complete a solution without backtracking. With $N$ variables and maximum constraint domain size $d$, the basic compatibility checks require $O(N{d}^2)$ time complexity in Big O notation, counting each binary constraint evaluation as one operation; evaluating bundle sums has its own input-dependent cost.