What is O(k)?

One write recomputes the derived values that depend on it. How many that is, k, sets the work, not how big the graph is, n.

Kernel: this.me 4.2.1 (npm).

n and k

Symbol	Meaning
n	Every value in the graph: facts and derived values.
k	The derived values that one write recomputed. Read it with `me.explain(path).meta.k`.

A derived value is declared once with ["="] and recomputes when one of its inputs changes. When you write a fact, the kernel follows the dependents of that path, and their dependents, and recomputes only those. That set is the write’s wave; its size is k. Values that do not read the written path, directly or through another derived value, are not touched.

So the propagation work of a write grows with k. Adding more unrelated values makes n bigger and leaves k where it was.

Example

import { ME } from "this.me";
const me = new ME() as any;

me.a(1);
me.b(2);
me["="]("c", "a + b");
me["="]("d", "c * 2");

for (let i = 0; i < 1000; i++) {   // 1,000 unrelated derived values
  me.other[i].x(i);
  me.other[i]["="]("y", "x + 1");
}

me.a(5);                            // one write
me("d");                            // 14
me.explain("d").meta;

Returns (timestamps shortened), run on this.me 4.2.1:

{
  "dependsOn": ["c"],
  "lastComputedAt": 1791911874286,
  "k": 2,
  "recomputed": ["c", "d"],
  "changed": ["c", "d"],
  "sourcePath": "a",
  "recomputedAt": 1791911874286
}

The graph has 1,002 derived values. The write to a recomputed two of them, c and d; none of the 1,000 other[i].y values was evaluated.

Reading a wave

Field	Meaning
`meta.k`	How many derived values the last wave that reached this path recomputed.
`meta.recomputed`	Those paths, in order (its length is `k`).
`meta.changed`	The subset of `recomputed` whose value actually changed. A value that recomputes to the same result is not in it.
`meta.sourcePath`	The write that started the wave.

Full return shape: me.explain(path). How paths are written and read: me.whatever(what).

What it does not say

O(k) is not “always fast”. If k is large, the write is large. In Extreme Fan-Out every one of 100,000 values reads the same root, so one write recomputes all 100,000.
It is about propagation. Other costs of a write are separate. In GTFS-Madrid, DELETE is still a store scan, so its time grows with the data even when k is small (GTFS-Madrid benchmark).
k counts recomputations, not changes. Use meta.changed to see which values moved.

Measured

GTFS-Madrid (benchmark). Real GTFS Madrid data shaped as .me paths and formulas, with CREATE / UPDATE / DELETE writes. Across scales, k per write stayed at p50 1 / p95 18 / max 27 while stop times grew 100× (2,364 → 236,400).

scale	stop_times	k p50 / p95 / max	kernel
1	2,364	1 / 18.5 / 27	this.me 4.2.1
10	23,640	1 / 18 / 27	this.me 4.2.1
100	236,400	1 / 18 / 27	this.me 4.1.0 (not re-run on 4.2.x)