What is the time complexity of the algorithm to check if a number is prime?
This is the algorithm :
bool isPrime (int number) {
if (number < 2) return false;
if (number == 2) return true;
if (number % 2 == 0) return false;
for (int i=3; (i*i) <= number; i+=2) {
if (number % i == 0 ) return false;
}
return true;
}
O(sqrt(n)) in the magnitude of the number, but only as long as you use int
Note that complexities for prime number related algorithms are often discussed with n as the length (in bits) of the number - and that you cannot assume things like comparing, adding, modulor or multiplying to be O(1), because with arbitrariy-precision numbers these operations become more expensive with the size of the number.
The best currently known algorithm runs in O((log n)^6)
Worst case - when the number is prime - is quite obvious O(sqrt(n)) Best case happens when number can be divided by 2,3,5,7,9. In these cases we will terminate the loop pretty soon in finite number of steps - O(1)
Now lets compute full average case for the algo:
On the interval [0,n] there are aprox n/ln(n) prime numbers.
The algo hits prime with probability of P1=1/ln(n)
The other numbers with probability of P2=1-ln(n)
Average case is O(sqrt(n))*1/ln(n)+O(1)*(1-ln(n)) We get rid of smaller part
=O(sqrt(n))/ln(n)
move ln(n) inside O()
=O(sqrt(n)/ln(n))
base of logarithm does not matter for big-O notation
= O(sqrt(n)/log(n))
The maximum execution time of this algorithm is O (sqrt (n)), which will be achieved if n is prime or the product of two large prime numbers.
Average execution time is tricky; I'd say something like O (sqrt (n) / log n), because there are not that many numbers with only large prime factors.
sqrt(number), this is enough info for you to figure out the rest...