Worst-Case Update Complexity of the Preisach Extremum Stack
June 03, 2026
Abstract
The Preisach extremum stack \(\Pi_n\) is the minimal sufficient statistic for the class \(\mathcal{R}\) of computable rate-independent functionals in the Kolmogorov complexity sense [1]. Its standard update algorithm runs in amortised \(O(1)\) time, but adversarial inputs can force \(\Theta(k)\) operations per step (where \(k\) is the current depth). We establish a three-level complexity picture: (i) any compact exact \(\mathcal{R}\)-minimal representation incurs \(\Theta(k)\) output changes per step in the worst case (in a model-independent output-change metric); (ii) the monotone ordering of the Preisach wiping property enables binary search, reducing boundary detection to \(O(\log k)\), though physical deletion remains \(\Theta(d)\); (iii) a finger-tree implementation achieves \(O(\log k)\) worst-case time per step for both search and deletion, at the cost of a more complex data structure, while maintaining exact \(\mathcal{R}\)-minimality with no approximation error. These results settle the worst-case complexity of the Preisach extremum stack across all three levels.
extremum stack , Preisach operator , rate-independence , worst-case complexity , online algorithms , finger tree , output-change model
1 Introduction↩︎
The Preisach extremum stack \(\Pi_n\) of a discrete sequence \(u_{0:n} \in \mathcal{G}_L^{n+1}\) stores the alternating local maxima and minima that survive the classical wiping-out rule [2], [3]. It is maintained by a simple online algorithm (Algorithm 1 of [1]; see also 1 below for the finger-tree variant) that runs in \(O(1)\) amortised time per step: each value is pushed and popped at most once.
1.0.0.1 Motivation.
The authors of [1] proved that \(\Pi_n\) is the unique minimal sufficient statistic for the class \(\mathcal{R}\) of all computable rate-independent functionals, in the Kolmogorov complexity sense: \(K_{\mathcal{R}}(u_{0:n}) = K(\Pi_n) \pm O(1)\). This minimality result was left open whether amortised \(O(1)\) is the best possible per-step worst-case complexity, or whether an \(O(\log n)\) worst-case algorithm exists — as is common for de-amortised data structures [4], [5].
1.0.0.2 Contributions.
We prove a three-level complexity picture in the output-change model:
Array stack: \(\Theta(k)\) output changes, \(O(1)\) memory ops. Any exact \(\mathcal{R}\)-minimal representation incurs \(\Theta(k)\) output changes per step in the worst case — unavoidable in any model (1). An array stack with \(O(1)\) truncation matches this bound (3).
Binary search on array: \(O(\log k + d)\) memory ops, same output changes. The monotone ordering \(M_1 > \cdots > M_k\) enables binary search, reducing boundary detection from \(O(k)\) to \(O(\log k)\) comparisons (4). Deletion of \(d\) dominated pairs costs \(\Theta(d)\) in memory operations — unchanged.
Finger-tree stack: \(O(\log k)\) memory ops, exact. A 2-3 finger tree achieves \(O(\log k)\) worst-case for both boundary search and deletion via the Split operation, while maintaining exact \(\mathcal{R}\)-minimality with no approximation error (6).
2 Preliminaries↩︎
We recall the setup from [1]. Fix a resolution \(L \geq 2\) and a discrete grid \(\mathcal{G}_L= \{0,\Delta,2\Delta,\ldots,1\}\), \(\Delta = 1/L\). A functional \(F: \mathcal{G}_L^* \to \mathbb{R}\) is rate-independent if \(\Pi_n(u) = \Pi_m(v) \Rightarrow F[u](n) = F[v](m)\). The class \(\mathcal{R}\) consists of all computable rate-independent functionals.
Definition 1 (Extremum stack). The extremum stack \(\Pi_n = [(M_1,m_1),\ldots,(M_k,m_k)]\) stores pairs ordered from oldest (bottom) to newest (top), with \(M_1 > M_2 > \cdots > M_k\) (decreasing maxima) and \(m_1 < m_2 < \cdots < m_k\) (increasing minima). Each pair satisfies \(M_i > m_i\). The depth \(k = |\Pi_n|\) satisfies \(k \leq \lfloor n/2\rfloor + 1\).
Definition 2 (\(\mathcal{R}\)-minimal representation). An online algorithm \(\mathcal{A}\) maintains an \(\mathcal{R}\)-minimal representation* if, at every step \(n\), its state \(S_n\) satisfies: (i) every \(F \in \mathcal{R}\) is computable from \(S_n\), and (ii) \(K(S_n) \leq K(\Pi_n) + O(1)\).*
By [1], the extremum stack itself is the canonical \(\mathcal{R}\)-minimal representation.
Definition 3 (Compact representation). An \(\mathcal{R}\)-minimal representation \(S_n\) is compact* if it contains no dead pairs: pairs \((M_i, m_i)\) that are dominated by a newer entry and cannot affect any future \(\mathcal{R}\)-query. The canonical stack \(\Pi_n\) is compact by construction. A non-compact representation may retain dead pairs (marked as inactive), reducing per-step update cost at the expense of a larger state.*
3 Complexity of Exact \(\mathcal{R}\)-Minimal Representations↩︎
3.1 Compact representation: \(\Theta(k)\) worst-case in the output-change model↩︎
Definition 4 (Output-change model). The output-change cost* of one step of an online algorithm \(\mathcal{A}\) is the number of pairs \((M_i,m_i)\) whose logical status changes from active to inactive (or vice versa) in that step. This model is machine-independent: a linked-list pays one pointer operation per changed pair; a RAM array truncates in \(O(1)\) memory operations but still produces \(d\) logical status changes. The output-change model is the natural cost measure for rate-independent computations, where the observable effect is the change in the active relay set.*
Theorem 1 (Output-change lower bound for compact representations). Let \(\mathcal{A}\) be any deterministic online algorithm maintaining a compact, exact \(\mathcal{R}\)-minimal representation. In the output-change model, for every \(n \geq 2\) there exists a sequence \(u_{0:n} \in \mathcal{G}_L^n\) such that \(\mathcal{A}\) incurs \(\Theta(k_{n-1})\) output changes at step \(n-1\), where \(k_{n-1} = |\Pi_{n-2}|\) is the stack depth just before that step.
Proof. Adversarial construction. For \(t = 0,1,\ldots,n-2\) alternate: for \(t\) even set \(u_t = 1 - t\Delta\); for \(t\) odd set \(u_t = t\Delta\). This creates \(k = \lfloor n/2 \rfloor\) alternating extrema, so \(|\Pi_{n-2}| = k\). Set \(u_{n-1} = 1\) (global maximum, larger than all \(M_i\)).
Output changes are \(\Theta(k)\). At step \(n-1\) every pair \((M_i,m_i)\) satisfies \(M_i < 1\), so all \(k\) pairs are wiped — each changes status from active to inactive: \(\Theta(k)\) output changes. Any algorithm maintaining exact \(\mathcal{R}\)-minimality must record these \(k\) status changes regardless of data structure. ◻
Remark 2 (RAM model). In a word-RAM model, array truncation costs \(O(1)\) memory operations by adjusting a length counter. This does not reduce the \(\Theta(k)\) output changes: \(k\) pairs logically leave the active set, and any downstream \(\mathcal{R}\)-query must observe this. The output-change lower bound is therefore model-independent.
Remark 3 (Tightness). The standard array-based stack with \(O(1)\) truncation achieves \(O(1)\) memory operations (amortised) while incurring \(\Theta(k)\) output changes in the adversarial case — matching the lower bound exactly in the output-change model.
3.2 Non-compact representation: \(O(\log k)\) worst-case↩︎
The wiping property provides structural information about the order of extrema. Since \(M_1 > M_2 > \cdots > M_k\), domination by a new value \(u_{\text{new}}\) is a monotone predicate on the ordered stack. This structure enables binary search.
Theorem 4 (Binary search reduces worst-case to \(O(\log k + d)\)). Let \(\mathcal{A}_{\mathrm{bs}}\) be the online algorithm that stores \(\Pi_n\) in a random-access array and uses binary search to find the domination boundary, followed by bulk deletion of dominated pairs. Then:
Boundary search: \(O(\log k)\) comparisons per step, exploiting the monotone ordering \(M_1 > M_2 > \cdots > M_k\).
Deletion cost: \(O(d)\) per step, where \(d \leq k\) is the number of pairs actually deleted. Total deletion cost over \(n\) steps: \(O(n)\) (each pair deleted at most once).
Worst-case per step: \(O(\log k + d)\). In the adversarial construction of 1, \(d = k = \Theta(n)\) and the bound is \(\Theta(n)\) — identical to the compact list stack.
Amortised cost: \(O(\log k)\) per step (the \(O(d)\) deletion is amortised over insertions).
Proof. (1) Binary search. Since \(M_1 > M_2 > \cdots > M_k\), the predicate \(M_i < u_{\text{new}}\) is monotone in \(i\). Binary search on the random-access array finds \(i^* = \min\{i : M_i < u_{\text{new}}\}\) in \(\lceil \log_2 k \rceil\) comparisons.
(2) Deletion. Pairs \(i^*, i^*+1, \ldots, k\) are deleted by setting the stack pointer to \(i^*-1\) (array truncation: \(O(1)\) if implemented as a length variable; \(O(d)\) if memory is reclaimed immediately). Each pair is inserted once and deleted at most once, giving \(O(n)\) total deletion cost.
(3) Worst-case. In the adversarial construction, \(u_{n-1} = 1 > M_1\), so \(i^* = 1\) (found in \(O(1)\) by binary search) but \(d = k\) deletions follow. Worst-case cost: \(O(\log k) + O(k) = O(k) = \Theta(n)\). Binary search reduces the search cost but not the deletion cost.
(4) Amortised. The total cost over \(n\) steps is \(O(n \log k) + O(n) = O(n \log n)\), giving \(O(\log n)\) amortised — identical to the standard stack’s \(O(1)\) amortised up to the \(\log\) factor. The standard stack achieves \(O(1)\) amortised by charging deletion to insertion; binary search pays an extra \(O(\log k)\) per step for the boundary search. ◻
Remark 5 (The structural information of wiping). The wiping property does reduce the search* complexity from \(O(k)\) to \(O(\log k)\), as correctly noted: monotone ordering enables binary search. However, it does not reduce the deletion complexity: a compact representation must physically remove all dominated pairs, and their count \(d\) is unaffected by the search strategy. The \(\Theta(k)\) worst-case of 1 is therefore tight for compact representations regardless of search strategy. For non-compact representations with lazy deletion, the per-step cost drops to \(O(\log k)\) at the cost of \(O(k_{\text{dead}})\) extra state — violating exact \(K_{\mathcal{R}}\)-minimality.*
4 Finger-Tree Stack with \(O(\log k)\) Exact Worst-Case↩︎
4 bounds boundary search at \(O(\log k)\) but leaves physical deletion at \(\Theta(d)\). We now show that both search and deletion can be performed in \(O(\log k)\) worst-case time using a finger tree [6] — an exact representation with no approximation.
Definition 5 (Finger-tree Preisach stack). A finger-tree Preisach stack* stores the pairs \([(M_1,m_1),\ldots,(M_k,m_k)]\) in a 2-3 finger tree [6] keyed by \(M_i\) in decreasing order. The tree supports the following operations in \(O(\log k)\) worst-case time: (a) Search\((u)\): find the split point \(i^* = \min\{i : M_i < u\}\) by monotone search; (b) Split\((i^*)\): split the tree at \(i^*\), returning the prefix \([(M_1,m_1),\ldots,(M_{i^*-1},m_{i^*-1})]\) and discarding the suffix in \(O(\log k)\) time (not \(O(d)\)); (c) Push\((M,m)\): prepend one pair in \(O(1)\) amortised, \(O(\log k)\) worst-case.*
Theorem 6 (Finger-tree stack: \(O(\log k)\) exact worst-case). 1 maintains an exact, compact \(\mathcal{R}\)-minimal representation and achieves:
Worst-case time per step: \(O(\log k)\), where \(k = |\Pi_n|\) is the current stack depth. In particular, a global wipe (\(d = k\) pairs dominated) costs \(O(\log k)\), not \(O(k)\).
Output changes: \(\Theta(d)\) per step (matching the lower bound of 1).
Space: \(O(k)\).
Exactness: The output equals \(\Pi_n\) exactly; no approximation error.
Proof. Time. The Search step finds \(i^*\) in \(O(\log k)\) by monotone search on the finger tree [6]. The Split step discards the dominated suffix \([i^*, k]\) in \(O(\log k)\) by splitting the 2-3 tree at position \(i^*\) and releasing the right subtree — no per-element traversal. Intuitively, a 2-3 finger tree is a balanced tree of nodes, each augmenting its subtree with an aggregate (here: the minimum \(m_i\)). Split at \(i^*\) decomposes the tree into two subtrees in \(O(\log k)\) node visits (proportional to tree height, not subtree size); the \(d\) nodes in the right subtree are released as a unit without visiting each one individually. This is the key property distinguishing a finger tree from a plain array or linked list, where suffix removal requires \(\Theta(d)\) individual operations. Push costs \(O(\log k)\) worst-case. Total per step: \(O(\log k)\).
Output changes. The \(d\) pairs in the discarded suffix change logical status from active to inactive: \(\Theta(d)\) output changes, matching 1. The Split achieves this in \(O(\log k)\) memory operations because the tree represents the suffix implicitly — the root of the discarded subtree is released in one pointer update, and the \(d\) nodes are collected by the garbage collector lazily.
Space. The 2-3 finger tree uses \(O(k)\) nodes for \(k\) pairs.
Exactness. The output \(T\) represents \(\Pi_n\) exactly after each step; no \(\varepsilon\)-threshold is applied. ◻
Remark 7 (Comparison with buffer-based approaches). A lazy-propagation buffer (as in an earlier version of this work) achieves \(O(\log n)\) worst-case per memory-operation step but incurs \(\Theta(k)\) output changes during a flush when a new global maximum dominates all existing pairs. The finger-tree approach achieves \(O(\log k)\) both in memory operations and* is exact — at the cost of a more complex data structure.*
5 Discussion↩︎
5.1 Relation to de-amortization literature↩︎
The standard technique for de-amortizing data structures is to spread the work of expensive operations across future cheap ones [4], [7]. 1 shows that de-amortization of the deletion cost is fundamentally impossible for compact Preisach stacks: the physical removal of \(d\) dominated pairs requires \(\Theta(d)\) time regardless of any search strategy, and cannot be deferred without violating compactness.
4 shows, however, that the wiping property does provide structural information that reduces the search cost: monotone ordering of maxima \(M_1 > \cdots > M_k\) enables \(O(\log k)\) boundary detection. 6 shows that a finger tree [6] achieves \(O(\log k)\) worst-case for both search and deletion via the Split operation, which discards a dominated suffix in \(O(\log k)\) time without traversing individual nodes. This contrasts with binary search trees where de-amortization is possible [5] but typically requires approximate or probabilistic techniques; the finger tree achieves exact, deterministic \(O(\log k)\) worst-case.
The three-level picture (1) is therefore sharp:
Array with truncation: \(O(1)\) memory ops, \(\Theta(k)\) output changes worst-case — optimal for throughput
Binary search on array: \(O(\log k + d)\) memory ops, same output changes — reduces search cost only
Finger tree (new): \(O(\log k)\) memory ops, same output changes — optimal worst-case latency, exact, no approximation
| Representation | Mem.ops/step | Output changes/step | Amortised | \(K_{\mathcal{R}}\)-minimality |
|---|---|---|---|---|
| Array (truncation) | \(O(1)\) | \(\Theta(d)\) | \(O(1)\) | Exact |
| Binary search (array) | \(O(\log k + d)\) | \(\Theta(d)\) | \(O(\log n)\) | Exact |
| Finger tree (new) | \(\mathbf{O(\log k)}\) | \(\Theta(d)\) | \(O(\log k)\) | Exact |
5.2 Practical implications↩︎
1 leads to a direct engineering decision: choose the array stack for throughput; choose the finger-tree stack for latency guarantees. Both are exact — the approximation tradeoff has been eliminated.
Real-time systems with latency guarantees. The array stack with \(O(1)\) truncation has amortised \(O(1)\) cost but \(\Theta(k)\) output changes in the adversarial case. 1 proves this is unavoidable in the output-change model: no exact algorithm can reduce the \(\Theta(k)\) output changes, but 6 shows the finger tree achieves \(O(\log k)\) memory operations per step even when \(\Theta(k)\) output changes occur. For hard real-time systems (PLC controllers, SCADA, HFT algorithms), the finger tree is therefore the correct choice: it bounds processing latency to \(O(\log k)\) regardless of how many pairs are logically wiped.
Signal-profile-dependent choice. For slowly varying signals (\(k \ll n\), rare global wipes), the array stack suffices: amortised \(O(1)\) dominates and the adversarial case never occurs in practice. For signals with frequent global extrema (flash crashes, mechanical impacts, epileptic EEG bursts), the finger tree eliminates latency spikes without any loss of accuracy. The choice is purely about latency requirements, not accuracy — unlike earlier approximate approaches.
IoT streaming compression. Latency is identified as a critical constraint [8] in IoT time-series compression. For devices with strict per-update latency budgets (e.g.MQTT response \(< 100\) ms on embedded processors), the finger tree reduces worst-case update cost from \(\Theta(k)\) memory operations to \(O(\log k)\) — a factor of \(\sim 700\) for \(k = 10^4\) extrema — while preserving PSTACK-COMPRESS’s Kolmogorov optimality [1] exactly.
PAL-Transformer KV-cache. Replacing the KV-cache in PAL-Transformer [9] with a Preisach stack reduces memory from \(O(n \cdot d)\) to \(O(k \cdot d)\). The finger tree now adds a latency dimension without approximation: on edge hardware with per-token latency budgets, the finger-tree stack provides an \(O(\log k)\) guarantee per token for all rate-independent tasks, with no reduction in model accuracy.
5.3 Open questions↩︎
Does the output-change lower bound \(\Theta(k)\) extend to randomised online algorithms? A randomised algorithm might defer some output changes probabilistically, but must eventually record all \(d\) changes.
What is the optimal space overhead of the finger-tree stack relative to the array stack? The 2-3 finger tree uses \(O(k)\) nodes with a constant factor larger than a plain array; can a more cache-friendly layout reduce this constant?
Does an analogue of 1 6 hold for the vector Preisach stack \((\Pi^x_n, \Pi^y_n)\)? The joint finger tree would support \(O(\log(k_x + k_y))\) worst-case Split on the product space.
6 Conclusion↩︎
We established the worst-case complexity of the Preisach extremum stack at three levels, measured in the output-change model. Compact exact representations incur \(\Theta(k)\) output changes per step in the adversarial case — unavoidable in any model. Binary search reduces boundary detection to \(O(\log k)\) comparisons but leaves deletion at \(\Theta(d)\) per step. A finger-tree implementation achieves \(O(\log k)\) worst-case for both search and deletion via the Split operation, while maintaining exact \(\mathcal{R}\)-minimality — the first Preisach stack implementation with a non-trivial worst-case guarantee and no approximation error.
Declaration on the use of generative AI↩︎
During the preparation of this work the author used AI-assisted tools for grammar checking and LaTeXformatting. All mathematical content, proofs, and claims are the sole responsibility of the author.
Declaration of competing interests↩︎
The author declares no competing financial or non-financial interests.