Runtime analysis of a "find the secret number" algorithm The algorithm task is to find an integer (range is not known). the function guess(num) returns one of three chars: '>','&lt;' 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 == "&gt;":
        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 &lt; secret &lt; 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!
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 &lt; \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.