Question

(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 the following 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 tightest possible lower bound that you can prove for Mystery and why? What is the tightest possible upper bound, assuming Primes(n)runs in quadratic time, that you can prove for Mystery and why? (b) Solve the 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 is convenient. Give one example of an algorithm whose time complexity can be expressed by this recurrence. Briefly explain what this algorithm does and how, and also what is its input.

Answer 1

Here is the solution to above problem . Please read code comments for more information

PLEASE GIVE A THUMBS UP!!!

Input: A natural number n > 1

//The Algorithm Mystery checks the initial condition wheather the input number is 2 or not , It basically checks if number is divisible 2
//Hence it is definetely not prime, It is not divisble by 2 the algorithm proceeds to check that if a number is prime or not USING Primes algorithm
//in order N time
Algorithm Mystery(n)
//checking if the number n is divisible by 2
if ( n mod 2 == 0 ) then //
if (n == 2) then //if number is 2 is prime
output "Input is a prime number"
else "Input is not a prime number" //If a number is divisible by 2 and it is not 2 hence it is prime
else
Primes(n) //This check a number is Prime or not O(N^2)

Input: A natural number n > 1

//The Algorithm Mystery checks the initial condition wheather the input number is 2 or not , It basically checks if number is divisible 2
//Hence it is definetely not prime, It is not divisble by 2 the algorithm proceeds to check that if a number is prime or not USING Primes algorithm
//in order N time
Algorithm Mystery(n)
//checking if the number n is divisible by 2
if ( n mod 2 == 0 ) then //
if (n == 2) then //if number is 2 is prime
output "Input is a prime number"
else "Input is not a prime number" //If a number is divisible by 2 and it is not 2 hence it is prime
else
Primes(n) //This check a number is Prime or not O(N)

Input: A natural number n > 1

//The Algorithm Mystery checks the initial condition wheather the input number is 2 or not , It basically checks if number is divisible 2
//Hence it is definetely not prime, It is not divisble by 2 the algorithm proceeds to check that if a number is prime or not USING Primes algorithm
//in order N time
Algorithm Mystery(n)
//checking if the number n is divisible by 2
if ( n mod 2 == 0 ) then //
if (n == 2) then //if number is 2 is prime
output "Input is a prime number"
else "Input is not a prime number" //If a number is divisible by 2 and it is not 2 hence it is prime
else
Primes(n) //This check a number is Prime or not O(N^2)

The tighest bound for mystery algorithm is O(N^2) since all it has are simple if conditions other than that it just calls the primes(n) function which takes O(N^2) time

b) T(N) = T(N/2) + 1

T(N) = T(N/4) + 1+1 //put value of T(N/2)

..

.

.

T(K) = T(N/2^k) + K

now solving for N/2^k =1 we get K = LOGN

Hence time complexity of T(N) =T(N/2) +1 is O(LOGN)

The Greatest common divisor has the time complexity represented by T(N/2) +1