(a) Assume that a polynomial-time primality testing algorithm, calledPrimes is available, which takes as input a...

60.1K

Verified Solution

Question

Programming

(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.

Answer & Explanation Solved by verified expert

3.9 Ratings (508 Votes)

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 Mysteryn checking if See Answer

Get Answers to Unlimited Questions

Join us to gain access to millions of questions and expert answers. Enjoy exclusive benefits tailored just for you!

Membership Benefits:

Unlimited Question Access with detailed Answers
Zin AI - 3 Million Words
10 Dall-E 3 Images
20 Plot Generations
Conversation with Dialogue Memory
No Ads, Ever!
Access to Our Best AI Platform: Flex AI - Your personal assistant for all your inquiries!

Become a Member