Logo
Home Study Material Contact Search
AI Chat FREE
  1. computer science
  2. programming
  3. (a) assume that a polynomial-time primality testin

(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: Zin AI - Your personal assistant for all your inquiries!
Become a Member

Other questions asked by students

Q

5 Nancy went to her local zoo that featured 24 monkey exhibits If these monkey...

Basic Math
Q

How does an autoclave kill microbes so efficiently?

Biology
Q

●Find most recent tariff rates for 5 food/agricultural commodities in UAE. ●Find at least three or five non-tariff barriers...

Economics
Q

Removing point A from the scatterplot will a change the correlation but not the regression...

Basic Math
Q

Find the divergence of the field F 4x 6y 5z i 8x 6y 7z j...

Calculus
Q

Use a graphing utility to graph the function and estimate its domain and range Then...

Calculus
Q

What are the solutions for the given equations belo 15 0 5

Algebra
Q

Trial Balance April 30, 2016 Account Debit Credit $27,500 40,400 3,000 1,400 68,800 Cash Accounts...

Accounting
Q

12. Portfolio Weights An investor owns $24,000 of Adobe Systems stock, $27,000 of Dow Chemical,...

Accounting
Q

If cash is $7,228, accounts receivable is $14,047,notes payable is $6,388, common stock is $1,290...

Accounting
Q

A major benefit of effective budgeting is that OA) it provides benchmarks to evaluate subsequent...

Accounting
Q

An example of an explicit transaction is? depreciation expense. ...

Accounting