Can somebody explain this to me about time complexity regarding the primality problem

user_13365591 0
Viewed 50

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.

theory time-complexity algorithm
4 Answers

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

user_21446690 
"{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.

user_53488750

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?

user_23194070

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.

user_167591160
Related