Cumulative checkpoint: algorithms and data structures

Amortized work is a bound on a sequence

A resizing append copies the existing $n$ elements, so its individual cost can be linear. Across growth capacities $1,2,4,\ldots$, the total copies before reaching $n$ elements form a geometric sum less than $2n$, up to the chosen initial-capacity convention. Add the $n$ new-element writes to obtain linear total work, hence constant amortized cost per append. This redistributes expensive steps across the sequence; it does not erase the latency spike of a particular resize or establish real-time behavior.

Maintain the partition outside the search interval

Start $lo=0,hi=6$. Midpoint 3 has value 5, so set $hi=3$. Midpoint 1 has value 2, so set $lo=2$. Midpoint 2 has value 5, so set $hi=2$. Return 2. All indices below $lo$ have values less than the target, and all indices at or above $hi$ have values at least the target. The uncertain interval shrinks until empty. Returning index 3 would find a matching value but violate the first-not-less-than contract.

Optimal substructure concerns the remaining amount

Greedy picks $6+1+1$, using three coins. The optimal choice $4+4$ uses two. Let $D(0)=0$ and $D(a)=1+\min_{c\le a}D(a-c)$ over allowed coins with reachable remainders; unreachable states have infinity. Any nonempty solution ends with some coin $c$, leaving amount $a-c$. If the remaining solution were not optimal, replacing it would improve the whole solution, so minimizing over possible last coins is valid. The recurrence optimizes coin count, not coin value or a greedy local preference.

Discovery is a tentative bound

The shortest route is $S\to B\to A\to G$ with cost $1+1+1=3$. A is first discovered through $S\to A$ at cost 4, but after settling B its cost improves to 2. Permanently fixing A on discovery would miss this improvement and could report a longer path. Nonnegative-edge Dijkstra reasoning applies to the minimum valid frontier distance, not to the first time a vertex is encountered.

Expected behavior depends on hashing assumptions

With $n$ keys in one chain, lookup can inspect all $n$ entries, and insertion that first checks for an existing key can also take $\Theta(n)$. A sequence of such insertions can have quadratic total comparison work. Increasing bucket count does not help if the hash function or adversarial key family still maps every key to the same bucket. A better distribution, keyed hash strategy in suitable settings, or a different worst-case data structure may be needed. Expected constant-time language must state its assumptions.

The movement model determines the lower bound

From $(0,0)$ to $(1,1)$, one diagonal costs 1 while Manhattan distance is 2, an overestimate. With unit-cost eight-neighbor moves, Chebyshev distance $\max(|\Delta x|,|\Delta y|)$ is a lower bound: each move changes each coordinate by at most one, and diagonal moves can reduce both gaps together. Obstacles can only remove routes or make them longer, so the unobstructed lower bound remains admissible. Different diagonal costs require another derivation rather than blindly reusing this formula.