The current page is What is O(k)? in the .me docs (this.me 4.2.1, with verified examples and benchmark figures by kernel version). This page is kept as an earlier version.
Cost tracks the dependency frontier, not the graph. Not a claim that it's cheap.
cost(mutation) = O(k), where k is the number of
paths that actually depend on what changed — independent of
n, the total size of the graph. This is a locality claim,
not a speed guarantee: when k itself is large, the cost is
genuinely large.
n = total graph size
k = |affected dependency frontier| for a given mutation
cost(mutation) = O(k)n = 100,000 dependents, all subscribed to one root.
| phase | measured |
|---|---|
| wiring 100,000 subscribers | 137,451.08 ms |
one mutation, k = 100,000 | 21,283.534 ms |
This is k at its worst: every one of 100,000 nodes
genuinely depends on the changed value, so all 100,000 recompute. Real
cost, ~21.3s, not hidden by the formula. O(k) does not mean
fast — it means proportional to k, and here k
is enormous.
n = 1,000,000 nodes.
| phase | measured |
|---|---|
| setup, 1,000,000 nodes | 21,899 ms |
one mutation, k = 6 | 4.346 ms |
| heap | ~533 MB |
This is the actual demonstration of O(k), not O(n):
a million-node graph, but the specific mutation tested only has 6 real
dependents — so it costs 4.346ms, not something scaled to a million.
n being huge did not touch this number. k did.
3,000 nodes, 300 iterations — whole-loop latency, not per-node. What explain() actually returns: me.explain().
| mode | p95 |
|---|---|
| baseline | 0.0154 ms |
with explain() | 0.0198 ms (+28.11%) |
Subscriber tracking and recompute-wave tracking were both refactored from
linear-scan array patterns to Set-backed structures —
confirmed in the kernel's git history (commit a186449):
// before
if (!list.includes(value)) list.push(value);
// after
set.add(value);
Applied in both cascade.ts's dependency graph and
derivation.ts's refSubscribers and recompute-wave
tracking. This is what makes membership checks and inserts
O(1) instead of O(k) on top of the already-real
O(k) traversal — removing a second, avoidable cost layered on
the first.