Time complexity of the program

Question

 #include<stdio.h>
 #include<time.h>

 int main()

  {

    clock_t start;
    double d;
    long int n,i,j;
    scanf("%ld",&n);
    n=100000;
    j=2;
    start=clock();
    printf("\n%ld",j);

       for(j=3;j<=n;j+=2)
       {
          for(i=3;i*i<=j;i+=2)

          if(j%i==0)
            break;

           if(i*i>j)
          printf("\n%ld",j);

        }
    d=(clock()-start)/(double)CLOCKS_PER_SEC;
    printf("\n%f",d);

}

I got the running time of 0.015 sec when n=100000 for the above program. I also implemented the Sieve of Eratosthenes algorithm in C and got the running time of 0.046 for n=100000.

How is my above algorithm faster than Sieve's algorithm that I have implemented.

What is the time complexity of my above program??

My sieve's implementation

 #define LISTSIZE 100000    //Number of integers to sieve<br>
 #include <stdio.h>
 #include <math.h>
 #include <time.h>

int main()
{   


    clock_t start;
    double d;
    long int list[LISTSIZE],i,j;
    int listMax = (int)sqrt(LISTSIZE), primeEstimate = (int)(LISTSIZE/log(LISTSIZE));

    for(int i=0; i < LISTSIZE; i++)
     list[i] = i+2;
    start=clock();

    for(i=0; i < listMax; i++)
    {
     //If the entry has been set to 0 ('removed'), skip it
     if(list[i] > 0)
     {
      //Remove all multiples of this prime
      //Starting from the next entry in the list
      //And going up in steps of size i
      for(j = i+1; j < LISTSIZE; j++)
      {
       if((list[j] % list[i]) == 0)
        list[j] = 0;
      }
     }
    }
    d=(clock()-start)/(double)CLOCKS_PER_SEC;

    //Output the primes
    int primesFound = 0;
    for(int i=0; i < LISTSIZE; i++)
    {
     if(list[i] > 0)
     {
      primesFound++;

      printf("%ld\n", list[i]);
     }
    }
    printf("\n%f",d);
    return 0;
}

Answer 1

There are a number of things that might influence your result. To be sure, we would need to see the code for your sieve implementation. Also, what is the resolution of the clock function on your computer? If the implementation does not allow for a high degree of accuracy at the millisecond level, then your results could be within the margin of error for your measurement.

I suspect the problem lies here:

            //Remove all multiples of this prime
            //Starting from the next entry in the list
            //And going up in steps of size i
            for(j = i+1; j < LISTSIZE; j++)
            {
                    if((list[j] % list[i]) == 0)
                            list[j] = 0;
            }

This is a poor way to remove all of the multiples of the prime number. Why not use the built in multiplication operator to remove the multiples? This version should be much faster:

            //Remove all multiples of this prime
            //Starting from the next entry in the list
            //And going up in steps of size i
            for(j = list[i]; j < LISTSIZE; j+=list[i])
            {
              list[j] = 0;
            }

Answer 2

Your sieve implementation is incorrect; that's the reason why it is so slow:

• you shouldn't make it an array of numbers, but an array of flags (you may still use int as the data type, but char would do as well)
• you shouldn't be using index shifts for the array, but list[i] should determine whether i is a prime or not (and not whether i+2 is a prime)
• you should start the elimination with i=2
• with these modifications, you should follow 1800 INFORMATION's advice, and cancel all multiples of i with a loop that goes in steps of i, not steps of 1

Answer 3

What is the time complexity of my above program??

To empirically measure the time complexity of your program, you need more than one data point. Run your program for multiple values of N, then make a graph of N vs. time. You can do this using a spreadsheet, GNUplot, or graph paper and pencil. You can also use software and/or plain old mathematics to find a polynomial curve that fits your data.

Non-empirically: much has been written (and lectured in computer science classes) about analyzing computational complexity. The Wikipedia article on computational complexity theory might provide some starting points for further reading.

Answer 4

Just for your time complexity:

You have an outer loop of ~LISTMAX iterations and an inner loop of max. LISTSIZE iterations. This means your complexity is

O(sqrt(n)*n)

where n = listsize. It is actually a bit lower since the inner loop reduces it's count eacht time and is only run for each unknown number. But that's difficult to calculate. Since the O-Notation offers an upper bound, O(sqrt(n)*n) should be ok.

Answer 5

The behaviour is difficult to predict, but you should take into account that accessing the memory is not cheap... it's probably faster to just calculate it again for small primes.

Answer 6

Those run times are too small to be meaningful. The system clock resolution is not accurate to that kind of level.

What you should do to get accurate timing information is run your algorithm in a loop. Repeat it a few thousand times to get the run time up to at least a second, then you can divide the time by the number of loops.