Java

Big-O Estimation

Primality: determine whether or not a large number n is prime. Assume the worst case, namely that n really is prime.

A) System.out.println("isPrime = " + isPrime(n); (where isPrime is defined by: static boolean isPrime(int n){ for(int i=2; i<=n/2; i++){ if( n%i == 0 ) return false; return true; }

B) boolean isPrime = true; for(int i=2; i*i <= n; i++){ if(n%i == 0) isPrime=false; } System.out.println("isPrime = " + isPrime);

Suppose that both A and B take 50 ms to find if 1007 is prime.

Estimate how long A and B will take to determine that 1,000,000,001 is prime.