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
Sis 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:
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.