(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.
Already registered? Login
Not Account? Sign up
Enter your email address to reset your password
Back to Login? Click here