(a) Assume that a polynomial-time primality testing algorithm,calledPrimes is available, which takes as input a single numbern>1 and outputs whethernis a primenumber or not. Now consider thefollowing algorithm:
Input: A natural number n > 1
Algorithm Mystery(n)
if ( n mod 2 == 0 ) then
if (n == 2) then
output ‘‘Input is a prime number’’
  else ‘‘Input is not a prime number’’
else
Primes(n)
What is Algorithm Mystery trying to achieve? What is tightestpossible lower bound that you can prove for Mystery and why? Whatis the tightest possible upper bound, assuming Primes(n)runs inquadratic time, that you can prove for Mystery and why? (b) Solvethe recurrence T(n) =T(n/2) + 1 with the initial condition T(1) =1. Show all steps. You may assume that is a power of 2 if it isconvenient. Give one example of an algorithm whose time complexitycan be expressed by this recurrence. Briefly explain what thisalgorithm does and how, and also what is its input.
