When should a telemetry API promise any local peak in O(log n) instead of the global maximum?

## The two contracts are not two speeds of one thing It is tempting to file this as "O(log n) versus O(n)" and pick the faster one. That framing is the mistake. The logarithmic slope-comparison search answers *"give me an index where the readings stop climbing"*. A linear scan answers *"give me the largest reading"*. These are different questions with different answers, and only one of them is what most consumers mean when they say "the peak". Choosing the cheap one is choosing to ship a weaker guarantee, so the decision belongs with whoever owns the contract, not with whoever is optimising the loop. ## When the cheap guarantee is genuinely free If the series is **guaranteed single-humped** — one ascent, one descent, by the physics of how it is produced, such as a climb-and-descent altitude profile for a single flight — then it has exactly one local maximum, and *any peak* is *the peak*. The two contracts coincide and the logarithmic search costs nothing in fidelity. The engineering work then moves upstream: where is that guarantee enforced? Options, in descending order of how well they age: 1. **In the shape of the data** — the ingest path only ever stores per-flight segments, each of which is single-humped by construction. 2. **Validated once at ingest** — an O(n) check when the series is written, amortised across every subsequent query. 3. **Assumed in a comment** — which is how you get a silently wrong number three quarters later, when someone starts concatenating two flights into one series and nothing complains. Per-query validation is the option that never makes sense: it costs the O(n) pass you were trying to avoid. ## When only the global maximum will do Any consumer that **compares** peaks — across flights, across time windows, against a threshold — needs the maximum, because comparing arbitrary local peaks compares noise. Alerting, capacity reporting and anything a customer sees are all in this bucket. So is anything that must be reproducible in an audit. If one consumer needs the maximum and others do not, expose two clearly named operations rather than one that is quietly the weaker of the two; a shared endpoint whose semantics are "whatever the fast path returns" is a defect waiting for its incident. ## Is the linear scan even a problem? Quantify before optimising. The relevant numbers are the series length, the query rate, and the latency budget. For a few thousand samples per series the scan is microseconds and the difference never leaves the noise floor of the network hop in front of it. The logarithmic search earns its keep in two situations that are worth naming explicitly: series large enough that a full pass dominates the request, and **series where reading a sample is itself expensive** — samples fetched over a network, decompressed per block, or computed on demand. In that second case the win is not asymptotic elegance, it is that you touch about log n samples instead of all of them, which is a real cost line. ## The stability trap The logarithmic answer is **not stable**. Two correct implementations — one probing the right neighbour, one the left; one flooring the midpoint, one not — return different valid peaks for the same input. That has three consequences a lead should anticipate: - Golden tests that pin a specific index become brittle for reasons unrelated to correctness, and get "fixed" by whoever is on call. - A downstream metric derived from the returned index can move without any data changing, purely because the search was refactored. That is the worst kind of production mystery: no input changed, and the diff looks harmless. - Caching and idempotency reasoning quietly weakens, because the same query can legitimately answer differently across versions. Mitigations, in order of preference: pick the stronger contract; or fix a documented tie-break rule (for example, always the leftmost qualifying peak) and test *that property* rather than one index; or document the non-determinism loudly at the API surface so consumers do not build on an accident. ## What the decision costs the team The last input is maintenance. The linear scan is three lines any reviewer verifies at a glance and extends for free when the next request arrives ("also give me the second-highest", "also the peak count"). The invariant-based search is correct for a reason that takes a paragraph to state, has a well-known infinite-loop mutation, and is the kind of code that gets subtly broken by a well-meaning refactor. If the measured win is small, the stronger contract and the simpler code are the same choice, which is usually the tell that it is the right one. ## How to say it in an interview Do not answer "logarithmic, obviously". Ask what the consumer means by peak, ask whether the input shape is guaranteed, ask whether the O(n) pass is actually on the critical path — then commit, and name the risk you accepted. The judgment being tested is whether you know that a cheaper algorithm can silently be a weaker promise.