On the query complexity of finding a local maximum point
Publication date
2000-11
Authors
Rastsvelaev, A.L.
Beklemishev, L.D.
Editors
Advisors
Supervisors
DOI
Document Type
Preprint
Metadata
Show full item recordCollections
License
No license information available
Abstract
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.
Keywords
computational complexity, decision trees, local maximum, Fibonacci numbers