(a) Design an algorithm that reveals some secret integer numberfrom the set {1, 2, ... , n} by guessing random numbers within thegiven range until the secret number has been guessed. Numbersshould be replaced after being guessed such that ?it is possible toguess 2 and then 2 again?, assuming 2 is in the given range. Thealgorithm should return both the secret number as well as thenumber of guesses taken.
(b) If possible, calculate the tightest Big-?O? approximationfor the average runtime complexity of the algorithm from part (a).If it is not possible, explain why not. Note: assume that choosinga random number takes ?O(1)? time.
(c) If possible, calculate the tightest Big-?O? approximationfor the worst case runtime complexity of the algorithm from part(a). If it is not possible, explain why not. Note: assume thatchoosing a random number takes ?O(1)? time.
(d) In a single run, is it possible that of the algorithm frompart (a) finds the secret number in fewer guesses than a standardbinary search algorithm? If so, please provide a concrete exampleof one such situation.
