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.

  • $\begingroup$ 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!). $\endgroup$
    – Raphael
    Jan 29 '14 at 20:40

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.

  • $\begingroup$ 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? $\endgroup$
    – SuperStamp
    Jan 29 '14 at 20:56
  • 1
    $\begingroup$ Exactly. That's the idea. $\endgroup$ Jan 29 '14 at 21:23

Your Answer

