Suppose we want to determine if a given positive integer n ? 2 is prime (meaning
ID: 3561252 • Letter: S
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.