# Thread: complexity of this algorithm in my program

1. ## complexity of this algorithm in my program

Code:
#include <stdio.h>
#include <math.h>
int primetest(int n){

int temp = n,i;

for(i = sqrt(n);i>=2;i--){

if(!(temp%i))

return 1;
}

return 0;
}
int MOD(int x,int y,int n){

unsigned long i,j;

if(x>=1000){

i=x/1000;

j=x%1000;

return (((i*y)%n)*1000+(j*y))%n;

}

else if(y>=1000){

i=y/1000;

j=y%1000;

return (((i*x)%n)*1000+(j*x))%n;
}
else{

return (x*y)%n;
}

}
int Fermat_test(int N,int a){

int i,temp,bit=0,binary[20],n,mod;

unsigned long pm[20];

if(primetest(N)){

n=N;

N=N-1;

while (N!=0){

bit++;

i=N%2;

binary[bit]=i;

N=N/2;
}

pm[0]=a%n;

mod=pow(a,binary[1]);

for(i=1;i<=bit-1;i++){

pm[i]=MOD(pm[i-1],pm[i-1],n);

if(binary[i+1]!=0){

mod=MOD(mod,pm[i],n);
}
}

if(mod==1){

return 1;
}
else{

return 0;
}
}
}
main()
{

int a,N,i;

FILE * fp;

fp=fopen("c:\\output.txt","w+");

printf("Enter the value of a: <=13 ");

fflush(stdout);

scanf("%d",&a);

for(i=a+1;i<=1000000;i++){

if(Fermat_test(i,a)==1){

fprintf(fp,"%d\n",i);
}
}

return 0;
}

we only consider this part of our program:

Code:
         if(primetest(N)){
n=N;
N=N-1;
while (N!=0){
bit++;
i=N%2;
binary[bit]=i;
N=N/2;
}
pm[0]=a%n;
mod=pow(a,binary[1]);
for(i=1;i<=bit-1;i++){
pm[i]=MOD(pm[i-1],pm[i-1],n);
if(binary[i+1]!=0){
mod=MOD(mod,pm[i],n);
}
}
}
what is the time complexity of this part? They asked about a function O(f(N))= g(N) and discuss the ratio g(N)/f(N) as N goes to infinity.

2. Originally Posted by silversand

we only consider this part of our program:

Code:
         if(primetest(N)){
n=N;
N=N-1;
while (N!=0){
bit++;
i=N%2;
binary[bit]=i;
N=N/2;
}
pm[0]=a%n;
mod=pow(a,binary[1]);
for(i=1;i<=bit-1;i++){
pm[i]=MOD(pm[i-1],pm[i-1],n);
if(binary[i+1]!=0){
mod=MOD(mod,pm[i],n);
}
}
}
what is the time complexity of this part? They asked about a function O(f(N))= g(N) and discuss the ratio g(N)/f(N) as N goes to infinity.
This fragment:

Code:
            while (N!=0){
bit++;
i=N%2;
binary[bit]=i;
N=N/2;
}
looks like it is finding the binary expansion of N, and has complexity O(log(N)).

Similarly this fragment:

Code:
             for(i=1;i<=bit-1;i++){
pm[i]=MOD(pm[i-1],pm[i-1],n);
if(binary[i+1]!=0){
mod=MOD(mod,pm[i],n);
}
}
has complexity O(length(bit))=O(log(N)).

The trouble is the the complexity of primetest(N) which has to be calculated then the problem becomes what range of N do you want the average complexity over, or do you want the worst case complexity...

CB