Most reactivity is O(n). O(k) reactivity is O(k).

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.

The Equations

O(n) vs O(k)

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.

How

Inverted Dependency Indexing.

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.

Why it matters

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):

• baseline p95: 0.0122ms
• with explain() p95: 0.0189ms
• overhead: +0.007ms

Faithful trace for 7 microseconds because k << n.

The formula

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.

Go deeper

• Inverted Dependency Indexing: suign.github.io/InvertedIndex.html
• Equations: suign.github.io/Equations.html#ok-reactivity
• Benchmark: me vs React vs Zustand

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.