Runtime analysis of a "find the secret number" algorithm

Question

The algorithm task is to find an integer (range is not known). the function guess(num) returns one of three chars: '>','<' or '='.
Find the secret number with O(logS) guesses, where S is the secret number. You can use find_secret(N1, N2) which operate with O(log(N2-N1)).. What it does is simply a binary search.

So, the algorithm implemented (with Python) as follows:

def find_secret2():
 low = 1
 high = 2
 answer = guess(high)
 while answer == ">":
 low *= 2
 high *= 2
 answer = guess(high)
 if answer == "=":
 return high
 return find_secret(low, high)

my thoughts about the complexity of this algorithm:

it takes O(logS) to reach the range where low < secret < high.
then, it takes O(log(high-low)) - because we're using find_secret(N1, N2) method.

I'll be glad if you could help me explain why the algorithm's complexity is O(logS) in a mathematical/rigorous way using the O-notation.
Thanks!

• Raphael: Please use LaTeX to typeset mathematics! Also, note that you never specify the game (does everybody know it?) and that you want the asymptotic runtime of an algorithm, not the complexity of a problem (different things!).

Answer 1

You're almost there. It takes $O(\log S)$ time for your while loop to finish (by the way, how would you go about proving that? You can try induction on $\lceil \log_2 S \rceil$ or on $\lfloor \log_2 S \rfloor,ドル one of them should work). Then $\mathrm{low} \leq S < \mathrm{high}$. Furthermore $\mathrm{low}$ and $\mathrm{high}$ are certain powers of two, and so you can relate $\mathrm{high}-\mathrm{low}$ to $S$. More concretely, you want to bound $\mathrm{high}-\mathrm{low}$ from above in terms of $S$. This is the part you're missing. Perhaps you should try a few concrete examples and then generalize.

• SuperStamp: For the second part, we note that 2ドル^n - 2^{n-1} = 2^{n-1}$. Therefore, it can be bounded by $O(log2^{n-1})=O(log(low))<O(logS)$. Right?
• Yuval Filmus: Exactly. That's the idea.