Worst-Case Update Complexity of the Preisach Extremum Stack

The Preisach extremum stack Πn is the minimal sucient statistic for the class R of computable rate-independent functionals in the Kolmogorov com-plexity sense [1]. Its standard update algorithm runs in amortised O(1) time, but adversarial inputs can force Θ(k) operations per step (where k is the cur-rent depth). We establish a three-level complexity picture : (i) any compact exact R-minimal representation incurs Θ(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 Θ(d); (iii) a fnger-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 R-minimality with no approximation error. These results settle the worst-case complexity of the Preisach extremum stack across all three levels.