A slower lookup is an observation, not yet an algorithm diagnosis.
The event table grew from roughly 100,000 rows to 1,000,000. A support lookup now scans records until it finds an event for a particular deployment. The team sees a longer request and suspects the scan. That is plausible, but the observed duration can also include disk reads, lock waits, cache misses, or more concurrent work.
Start with a model that isolates one thing: the number of record comparisons in a
worst-case lookup. A scan over n records may inspect all n. If
records are ordered by the search key, binary search can discard about half the remaining
candidates after each comparison. These counts describe algorithmic work; they do not yet
tell us whether either implementation is the measured bottleneck.
- Population
- 1,000,000 event records in the searched history.
- Current method
- Scan records until a match; a miss can inspect every record.
- Proposed method
- Search an ordered index by deployment ID or timestamp.
- Question
- How does comparison work scale, and what must be true for binary search?
The shape tells you how additional input changes the modeled work.
For a linear scan, doubling the number of records can double the
worst-case comparisons: n. If every record must be inspected once, this is
the direct count. An early match can make one particular search cheaper, but a miss or
last-position match still reaches the worst case.
For logarithmic binary search, each comparison halves the remaining
sorted candidate range. After k halvings, at most n / 2ᵏ candidates remain. The count needed to narrow that range to about one is proportional to log₂(n). At a million records, the exact worst-case count under this lesson's
comparison convention is 20: 2¹⁹ < 1,000,000 ≤ 2²⁰.
For exponential growth, a quantity multiplies by a fixed factor each
step. A request tree in which every call makes two child calls has 1 call at depth 0, 2 at
depth 1, 4 at depth 2, and so on. Counting all levels through depth d gives 1 + 2 + 4 + … + 2ᵈ = 2^(d+1) − 1. This can model an unbounded branching
fan-out, but real systems may cap concurrency, deduplicate work, stop early, or use
different branching.
O(n), O(log n), and O(2ⁿ) are common asymptotic
notations. The base of a logarithm changes its numeric value by a constant factor, so
computer science often writes O(log n) without a base. Big-O also suppresses constant
factors and lower-order terms: it compares long-run scaling, not small-input speed or actual
milliseconds.
| Records, n | Linear scan, n | Binary search | Comparison |
|---|---|---|---|
| 10 | 10 | 4 | 3× as many scan comparisons at this scale |
| 1,000 | 1,000 | 10 | 100× as many scan comparisons at this scale |
| 1,000,000 | 1,000,000 | 20 | 50,000× as many scan comparisons at this scale |
| 1,000,000,000 | 1,000,000,000 | 30 | 33,333,333× as many scan comparisons at this scale |
Try a larger history and a deeper fan-out.
Counts are illustrative worst-case comparisons and full-tree calls, not timings.
This lab assumes one comparison per inspected candidate and a full binary call tree. It does not model CPU cost, memory, disk I/O, cache behavior, concurrency limits, or early exits.
At 1,000,000 records, the modeled counts are 1,000,000 scan comparisons versus 20 binary comparisons. At depth 10, a full binary fan-out has 2,047 nodes total. Change one input at a time: the lookup comparisons depend on the number of records, while the fan-out count depends on branching depth. The models answer different questions and have different units of work.
The faster comparison model needs a data contract.
Binary search depends on ordering. If the index is not sorted by the key being searched, a comparison cannot safely eliminate half the candidates. A mutable event stream also needs a plan for inserting new records and keeping the index current. That maintenance consumes storage and write work, and an index lookup may involve I/O that a sequential scan avoids.
A small collection may be cheaper to scan because setup and access overhead matter. A scan may also be necessary when the query asks for every record or applies a condition that the index does not cover. The model says how comparisons scale under specified operations; the workload tells you whether those operations dominate.
Likewise, the exponential fan-out model assumes every node always creates exactly two child calls. A concurrency cap can reduce simultaneous work without reducing total work. Caching, deduplication, and early termination can change total calls. Instrument the actual request graph before describing its growth.
Count the work while keeping the model visible.
The functions below calculate worst-case comparison counts by repeatedly halving the remaining candidate count, plus total calls in a full binary fan-out tree. They do not run a real search or dispatch requests. The loop makes the logarithmic process concrete; the closed-form sum makes the fan-out assumption inspectable.
Both versions validate their inputs and return counts, not timings.
export type LookupWork = {
items: number;
linearComparisons: number;
binaryComparisons: number;
};
function requireNonNegativeSafeInteger(value: number, name: string): void {
if (!Number.isSafeInteger(value) || value < 0) {
throw new Error(`${name} must be a non-negative safe integer`);
}
}
/** Worst-case record comparisons for a scan that may inspect every item. */
export function linearWorstCaseComparisons(items: number): number {
requireNonNegativeSafeInteger(items, 'items');
return items;
}
/** Worst-case comparisons for binary search over a sorted array of this size. */
export function binaryWorstCaseComparisons(items: number): number {
requireNonNegativeSafeInteger(items, 'items');
let remaining = items;
let comparisons = 0;
while (remaining > 0) {
comparisons += 1;
remaining = Math.floor(remaining / 2);
}
return comparisons;
}
export function compareLookupWork(items: number): LookupWork {
return {
items,
linearComparisons: linearWorstCaseComparisons(items),
binaryComparisons: binaryWorstCaseComparisons(items)
};
}
/** Calls in a full binary fan-out tree, counting the root request and every child call. */
export function fullBinaryFanoutCalls(depth: number): number {
if (!Number.isSafeInteger(depth) || depth < 0 || depth > 30) {
throw new Error('depth must be an integer from 0 through 30');
}
return 2 ** (depth + 1) - 1;
}
package mathpractice
import (
"errors"
"math"
)
type LookupWork struct {
Items int64
LinearComparisons int64
BinaryComparisons int64
}
func validItems(items int64) bool {
return items >= 0
}
// LinearWorstCaseComparisons counts a scan that may inspect every item.
func LinearWorstCaseComparisons(items int64) (int64, error) {
if !validItems(items) {
return 0, errors.New("items must be non-negative")
}
return items, nil
}
// BinaryWorstCaseComparisons counts comparisons for binary search over a sorted array.
func BinaryWorstCaseComparisons(items int64) (int64, error) {
if !validItems(items) {
return 0, errors.New("items must be non-negative")
}
var comparisons int64
for remaining := items; remaining > 0; remaining /= 2 {
comparisons++
}
return comparisons, nil
}
func CompareLookupWork(items int64) (LookupWork, error) {
linear, err := LinearWorstCaseComparisons(items)
if err != nil {
return LookupWork{}, err
}
binary, err := BinaryWorstCaseComparisons(items)
if err != nil {
return LookupWork{}, err
}
return LookupWork{Items: items, LinearComparisons: linear, BinaryComparisons: binary}, nil
}
// FullBinaryFanoutCalls counts nodes in a full binary tree through the given edge depth.
func FullBinaryFanoutCalls(depth int) (int64, error) {
if depth < 0 || depth > 30 {
return 0, errors.New("depth must be from 0 through 30")
}
return int64(math.Ldexp(1, depth+1) - 1), nil
}
Use the model to decide what evidence would settle the question.
For the event lookup, capture the query plan, rows examined, index hit behavior, and latency for representative event histories. Compare a match near the beginning, a match near the end, and a miss. Keep write and index-maintenance cost in the same review. If the suspected fan-out is involved, trace one request ID and count actual downstream calls at each depth.
Suppose each request fans out to three children instead of two through edge depth 4. How
many total calls does the full tree contain? Use 1 + 3 + 9 + 27 + 81 = 121.
Then name one piece of trace or configuration evidence you would need before claiming the
live service uses that model.