What is the order of complexity (Big O) of this code
I originally thought the complexity was O (n ^ 3) because the inner loop goes to i * i, but now I think the complexity is O (n ^ 2) because of the break statement.
What do you think?
#include <stdio.h>
int main()
{
int i,k,l,m;
unsigned int j;
l=0;
for (i=3; i<65535;i+= 2) {
k=1;
for (j=3; j <= i*i; j += 2) {
if (j==i) continue;
if(i%j ==0) {
k=0;
break;
}
}
if (k) { l++; }
}
printf("%i\n", l);
return 0;
}
source to share
The inner loop is O (N ^ 2) for primes, but fast for non-prime numbers (worst case O (N ^ 1/2) because you only need to search up to sqrt (N)).
The number of primes, however, is small compared to the number of primes. An approximation of the number of primes to X: X / log (X) as shown in this reference link.
So, throwing away non-zero numbers as irrelevant, there are N / log (N) primes and each inner loop takes O (N ^ 2) time, so the total time is O (N ^ 3 / log (N)).
source to share
for (j=3; j <= i*i; j += 2) {
if (j==i) continue;
if(i%j ==0) {
k=0;
break;
}
}
Without j == i
here j = 3,5,7,9,11,13,15,17 .... 65535. This means that j will contain all primes up to 65535 other than 2. There is math here. J <i * i. if i is a power of 2 or a prime number, then the j loop will be executed completely, but we can neglect the power of 2, since i is always odd. For any i at some point i = j [ O (n) complexity]
If I am a consonant, then i% j == 0 will happen quickly. As JS1 pointed out, loop j will take n / logn neglecting j == i.
So total time complexity = O (N * 2 / logn)
source to share