We are covering the class P in my class and this one part is tripping me up regarding if the primality problem is in P

Our program:

"{prime(x): i =2; while i < x { if n mod i == 0 { return 0 } i   } return 1 }"

Complexity for the program: If x is n digits long, then x is in the rough vicinity of 10^n . (Assuming no leading 0s, 10^n−1 ≤ x < 10^n.) The division algorithm that you learned in elementary school divides an m-digit number by an n-digit number in time O(mn). Puting that all together, we find that our algorithm for testing whether an integer is prime takes time O(n^2 10^n).

My questions: Where in the world does the professor get that x is 10^n, for example if x is 17 how does that turn into x being 10^2 = 100 operations long. Furthermore where is the n^2 coming from in the final big O notation.

CodePudding user response：

This trial division algorithm has to try x−2 divisors (i.e., Θ(10ⁿ) of them) when x is prime. The vast majority of these divisors have n or n−1 digits, so each division takes Θ(n²) time on average since m = Θ(n).

CodePudding user response：

"{prime(x): i =2; while i < x { if n mod i == 0 { return 0 } i   } return 1 }"

I mean with n you mean x, so your code should look like

prime(x){
    if(x == 2) return 0;
    for(int i = 2; i < x; i  )
        if(x mod i == 0) return 0
    return 1
}

This algorithm is the naive solution, which costs O(x).

It tests all natural numbers from 2 up to x. Supposing modulo is a constant time operation, you will do x - 1 operations (in worst case), hence O(x - 1) = O(x).

Obviously there are better solutions, like evaluating sieves to precompute primes so that you don't need to divide x for every other natural number.

CodePudding user response：

Where in the world does the professor get that x is 10^n

They don't.

What they actually said is:

If x is n digits long, then x is in the rough vicinity of 10^n

In your case it's off by a factor of 100/17≈5.9. But that's a constant factor (and not a big one). In the worst case, it's off by factor 10. And in complexity classes we ignore such constant factors, so it doesn't matter for their analysis.

CodePudding user response：

Well, primality problem is in P, see AKS Test for details

However, naive algorithm (that is in the question) is not in P. For given x we have

Time complexity t = O(x):

{prime(x): 
   i = 2; 
   
   while i < x { # we loop x - 2 times, t = O(x) 
     if n mod i == 0 { 
       return 0 
     }

     i   
   } 
   
   return 1 
}

Size of the problem s = O(log(x)) - we have to provide all digits to write x:

x = 123456789 # size is not 123456789, but 27 bits (or 9 digits)

So time complexity t from size of the problem s is O(2^s) if size s is in bits or O(10^s) if size s is in decimal digits. That is definitely not polynomial.

Let's have a look at your example: if x is n digits long (log10(x)), t will be ~ 10^n:

                x : size (digits) :              time
 ----------------------------------------------------
               17 :  1.23         :                15 # your example
 ~ 17_000_000_000 : 10.23         :  ~ 17_000_000_000 # just 10 times longer

Can you see exponent time ~ f(size) now?