Suppose we want to determine if a given positive integer n ? 2 is prime (meaning

Question

Suppose we want to determine if a given positive integer n ? 2 is prime (meaning the only numbers that divide it evenly are itself and 1). Here is one algorithm for the problem:

for i = 2 to n/2 do
if i divides n evenly then
   return false
return true

You may assume that arithmetic operations take O(1) time and that this is always called with a valid input value, although note that n is not necessarily a C++ int type (it could be more than 32 bits, for example).

(a) What is the runtime of this algorithm in terms of n, the input value?

(b) Is this a polynomial time algorithm, as per the definition from lecture and from the reading? Why or why not?

Explanation / Answer

1) it has order of O(n/2)= O(n)

2) It is linear time algorithm O(n).

An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm, i.e., T(n)=O(nk) for some constant k.

The algorithm runs in strongly polynomial time if

the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and

the space used by the algorithm is bounded by a polynomial in the size of the input.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.