On the query complexity of finding a local maximum point
We calculate the minimal number of queries sufficient to find a local maximum point of a function on a discrete interval, for a model with M parallel queries, M greater than or equal to 1. Matching upper and lower bounds are obtained. The bounds are formulated in terms of certain Fibonacci type sequences of numbers. (C) 2002 Elsevier Science B.V. All rights reserved.
computational complexity decision trees local maximum search fibonacci numbers