When you mutate one piece of state, the system should only do work proportional to how many things actually depend on it — not the size of the whole graph.
cost(mutation) = O(k) where k = |affected frontier|cost(mutation) = O(n) where n = |entire graph| ← React, Zustand, most stores
That’s it.
O(n): You change price. The framework scans 3000 components/nodes to find who uses price.
O(k): You change price. The runtime jumps directly to the 3 nodes that depend on price. It never sees the other 2997.
Inverted Dependency Indexing.
Instead of storing derived → sources, we maintain:
source path → set of dependent derived paths
On write to p:
T(Δp) = O(|Reach_D(p)| + C_eval)
We follow the frontier, we don’t scan.
Because explainability becomes free.
In .me:
me['!'].explain('order.total')// → { value, expr, inputs, dependsOn, recomputed, sourcePath }Returning the computation trace is a lookup over the index — not a second pass.
Benchmark (3000 nodes, 300 mutations):
Faithful trace for 7 microseconds because k << n.
I = (path, ciphertext, T, A, C)k = |Reach_D(p)|cost = O(k)
Readability (A) is not topology (T). Capability (C) is not identity. And cost is not size.
O(k) is not an optimization. It’s a different complexity class.
What is O(k) Reactivity? was originally published in Coinmonks on Medium, where people are continuing the conversation by highlighting and responding to this story.
