(a) Design an algorithm that reveals some secret integer number from the set {1, 2, ... , n} by guessing random numbers within the given range until the secret number has been guessed. Numbers should...

(a) Design an algorithm that reveals some secret integer number from the set {1, 2, ... , n} by guessing random numbers within the given range until the secret number has been guessed. Numbers should be replaced after being guessed such that ​it is possible to guess 2 and then 2 again​, assuming 2 is in the given range. The algorithm should return both the secret number as well as the number of guesses taken.

(b) If possible, calculate the tightest Big-​O​ approximation for the average runtime complexity of the algorithm from part (a). If it is not possible, explain why not. Note: assume that choosing a random number takes ​O(1)​ time.

(c) If possible, calculate the tightest Big-​O​ approximation for the worst case runtime complexity of the algorithm from part (a). If it is not possible, explain why not. Note: assume that choosing a random number takes ​O(1)​ time.

(d) In a single run, is it possible that of the algorithm from part (a) finds the secret number in fewer guesses than a standard binary search algorithm? If so, please provide a concrete example of one such situation.