It seems that the problem involves two parts:
1) To find an upper bound
2) Then divide the remaining region in halves until the number is found.
The first observation that I have is that given that the secret number s is chosen, the first step can be completed arbitrarily quickly. One could use a function that rises arbitrarily fast. Imagine for example the function taking k to the Ackerman function A(2,2,k). That rises so fast it's incomprehensible, but really one could easily produce a function which rises faster still (the algorithm that picks s first!). The problem is, though, of how fast a fixed algorithm is for random s. If s is truly chosen at random from the positive integers, this leads to problems. Fix your putative algorithm. Suppose for the moment that it starts at 0 (it is not going to matter where it starts) What is the probability that the kth number that your function spits out is less than a random integer? 100% After all, how many integers are greater than any given integer?
Therefore, no growth function is any better on average at finding the upper bound than any other. Therefore step 1) is an insoluble problem. The problem should have been specified in some other way in order for it to make sense.
However, the second step involves log_2(n) time (in the worst-case-scenario and still O(log n) in general) where n is the upper bound --the output of step 1-- which means that the time to complete the algorithm is (Time of step 1 to find n) + O(log n). IF the problem made sense and it was the case that step 1) were soluble, then it would matter how fast step 1 is countered by the degree to which step 1 tends to overshoot the secret number --because overshooting by k has the penalty of log(k) extra operations.
Is there are framework in which question 1 makes sense? It would make sense if there were a given probability distribution on the integers (a function on the positive integers whose sum over all integers = 1, for example choose the function f(n) = 6/(n^2 * pi^2)) A probability distribution gives you a way of answering the question: "what proportion of the positive integers are greater than k?"
The first observation that I have is that given that the secret number s is chosen, the first step can be completed arbitrarily quickly. One could use a function that rises arbitrarily fast. Imagine for example the function taking k to the Ackerman function A(2,2,k). That rises so fast it's incomprehensible, but really one could easily produce a function which rises faster still (the algorithm that picks s first!). The problem is, though, of how fast a fixed algorithm is for random s. If s is truly chosen at random from the positive integers, this leads to problems. Fix your putative algorithm. Suppose for the moment that it starts at 0 (it is not going to matter where it starts) What is the probability that the kth number that your function spits out is less than a random integer? 100% After all, how many integers are greater than any given integer?
Therefore, no growth function is any better on average at finding the upper bound than any other. Therefore step 1) is an insoluble problem. The problem should have been specified in some other way in order for it to make sense.
However, the second step involves log_2(n) time (in the worst-case-scenario and still O(log n) in general) where n is the upper bound --the output of step 1-- which means that the time to complete the algorithm is (Time of step 1 to find n) + O(log n). IF the problem made sense and it was the case that step 1) were soluble, then it would matter how fast step 1 is countered by the degree to which step 1 tends to overshoot the secret number --because overshooting by k has the penalty of log(k) extra operations.
Is there are framework in which question 1 makes sense? It would make sense if there were a given probability distribution on the integers (a function on the positive integers whose sum over all integers = 1, for example choose the function f(n) = 6/(n^2 * pi^2)) A probability distribution gives you a way of answering the question: "what proportion of the positive integers are greater than k?"