Sort, size-k heap, or quickselect — which survives an unbounded stream of price updates?

## Offline versus online, precisely An **offline** algorithm requires the whole input available before it can produce a correct answer, and usually requires random access to it. An **online** (streaming) algorithm consumes the input as a forward sequence, one element at a time, and can report a correct answer for everything seen so far at any point. Selection has both kinds of solution, and the regime — not the asymptotics — decides which you may use. ## Why the full sort is out A comparison sort is defined over a complete multiset. It cannot commit to the smallest element until it has seen the last arrival, because the next record may be smaller than everything so far. On an unbounded feed it therefore never terminates, and on a merely very large feed it needs all `n` records materialized. That is not a constant-factor concern; it is a correctness and residency concern. (The offline half of the same task — a catalog sitting on disk, too big for memory — is the case sorting *does* solve, via disk-backed merging strategies. That is a different regime and a different discussion; the point here is that neither regime is the streaming one.) ## Why quickselect is out Quickselect's cost model depends on partitioning a range and then narrowing to one side. That requires two things a stream does not give you: the whole range present at once, and random access so the algorithm can revisit shrinking sub-ranges. It also mutates the buffer it partitions, and there is no buffer to mutate when records arrive and are gone. Its expected O(n) — the best asymptotic of the three — is simply unavailable here, which is the cleanest illustration of why preconditions must be quoted alongside complexity. ## Why the bounded candidate structure survives A structure holding the best `k` candidates so far, with instant access to the *worst* of them, needs only: - one comparison per arriving record against that worst candidate, - an update only when the arrival wins, costing O(log k), - and O(k) resident state, independent of how many records the feed has produced. That gives O(n log k) over `n` arrivals, and the key operational property: the answer for everything seen so far is always available. A dashboard asking "what are the 100 cheapest right now?" can be served between any two arrivals. The memory ceiling is a design parameter — `k`, not `n` — which is exactly what you need when the feed's size is unknown. ## The caveat a senior candidate raises unprompted All of the above assumes an **append-only** stream: each event is a new record, and a record once discarded is never relevant again. Real price feeds are not like that. Two events break the model: 1. **Revision.** A product you discarded three hours ago drops its price and now belongs in the answer. Your k-sized retained set never saw it and cannot know. Retaining `k` items is only sufficient when discarded items cannot re-qualify. 2. **Removal.** A product currently inside the retained set is delisted. Removing an arbitrary interior element is not the operation the structure is optimized for, and the k-th slot must be refilled from data you no longer hold. Both push you toward one of three designs: retain more than `k` and accept a bounded staleness window; keep a durable, queryable store and re-run an offline selection on a schedule; or accept an approximate answer with a documented error bound. Which of those you take is a product decision about how wrong the number is allowed to be and for how long — and stating it as a product decision, rather than reaching for a cleverer structure, is the senior move. ## Cross-checking the regimes | Regime | Full sort | Bounded candidate heap | Quickselect | |---|---|---|---| | In-memory, one-shot, buffer you own | Works; gives ranking | Works | Works, usually fastest on average | | In-memory, input must not change | Works if sorting a copy | Works; read-only | Needs an O(n) copy first | | Too large for memory, durable store | Works via disk-backed strategies | Works if it can be scanned | Not usable directly | | Unbounded append-only stream | Not usable | Works; O(k) state | Not usable | | Stream with revisions and removals | Not usable | Not sufficient alone | Not usable | ## The register that lands "On a live feed only the bounded candidate scan works — one pass, k items of state, answerable at any moment; the other two need the whole input resident with random access. But I would check whether the feed revises prices, because if a record I already dropped can become cheap again, a k-sized retained set is quietly wrong, and I would rather agree on a staleness budget than ship a number nobody can defend."