The following algorithm determines whether a given natural number N is prime: for each integer k...

 

Transcribed Image Text:

The following algorithm determines whether a given natural number N is prime: for each integer k from 2 to [√n] do if k | N then return "N is not prime" end if end for return "N is prime" (a) Suppose that checking whether k | N takes time O (log² (N)) time. What is the running time of this algorithm, as a function of N? You do not need to give a proof. (b) Suppose N is given in binary. What is the running time of the algorithm, as a function of the input size? (Hint: The input is simply N in binary, so the input size is just the length of the binary representation of N.) (c) Is this algorithm efficient? Does it run in polynomial time? The following algorithm determines whether a given natural number N is prime: for each integer k from 2 to [√n] do if k | N then return "N is not prime" end if end for return "N is prime" (a) Suppose that checking whether k | N takes time O (log² (N)) time. What is the running time of this algorithm, as a function of N? You do not need to give a proof. (b) Suppose N is given in binary. What is the running time of the algorithm, as a function of the input size? (Hint: The input is simply N in binary, so the input size is just the length of the binary representation of N.) (c) Is this algorithm efficient? Does it run in polynomial time? The following algorithm determines whether a given natural number N is prime: for each integer k from 2 to [√n] do if k | N then return "N is not prime" end if end for return "N is prime" (a) Suppose that checking whether k | N takes time O (log² (N)) time. What is the running time of this algorithm, as a function of N? You do not need to give a proof. (b) Suppose N is given in binary. What is the running time of the algorithm, as a function of the input size? (Hint: The input is simply N in binary, so the input size is just the length of the binary representation of N.) (c) Is this algorithm efficient? Does it run in polynomial time?

Answer rating: 100% (QA)

a The running time of the algorithm as a function of N can be expressed as ON log2N This is becau... View the full answer