On the query complexity of finding a local maximum point
A.L. Rastsvelaev, Lev D. Beklemishev · Utrecht University Repository (Utrecht University) · 2000
We calculate the minimal number of queries sufficient to find a local maximum point of a functiun on a discrete interval for a model with M parallel queries, M≥1. Matching upper and lower bounds are obtained. The bounds are formulated in terms of certain Fibonacci type sequences of numbers.