Optimization of active algorithms for recovery of monotonic functions from Hölder's class (Q1333246)

Let \(H^ \alpha\) be the class of all functions \(f\in C([a,b])\) satisfying for \(0< \alpha\leq 1\) the condition \(| f(x')- f(x'')|\leq | x'- x''|^ \alpha\), \(x',x''\in [a,b]\) and let \(H^ \alpha_ m\) be the set of monotonic functions in \(H^ \alpha\). The relationship of passive and active algorithms in problems of recovery of functions is considered. The author proves that bisection is optimal among all active algorithms in the problem of recovery of functions \(f\in H^ \alpha_ m\) with metric \(C\) and when \(0< \alpha<1\) it achieves the best order \(O(N^{- 1}\log_ 2 N)\) on the set \(H^ \alpha_ m\).