There are lots of reasons to expect logarithmic (at best) returns to algorithms like best-of-k: lesswrong.com/posts/qPX…

For various reasons, I’d expect somewhat worse than logarithmic. These days I’m especially (and really only?) interested in things which scale better than that!