Time complexity of a sorting algorithm
- by Passonate Learner
The two programs below get n integers from file and calculates the sum of ath to bth integers q(number of question) times. I think the upper program has worse time complexity than the lower, but I'm having problems calculating the time complexity of these two algorithms.
[input sample]
5 3
5 4 3 2 1
2 3
3 4
2 4
[output sample]
7
5
9
Program 1:
#include <stdio.h>
FILE *in=fopen("input.txt","r");
FILE *out=fopen("output.txt","w");
int n,q,a,b,sum;
int data[1000];
int main()
int i,j;
fscanf(in,"%d%d",&n,&q);
for(i=1;i<=n;i++) fscanf(in,"%d",&data[i]);
for i=0;i<q;i++)
{
fscanf(in,"%d%d",&a,&b);
sum=0;
for(j=a;j<=b;j++) sum+=data[j];
fprintf(out,"%d\n",sum);
}
return 0;
}
Program 2:
#include <stdio.h>
FILE *in=fopen("input.txt","r");
FILE *out=fopen("output.txt","w");
int n,q,a,b;
int data[1000];
int sum[1000];
int main()
{
int i,j;
fscanf(in,"%d%d",&n,&q);
for(i=1;i<=n;i++) fscanf(in,"%d",&data[i]);
for(i=1;i<=n;i++) sum[i]=sum[i-1]+data[i];
for(i=0;i<q;i++)
{
fscanf(in,"%d%d",&a,&b);
fprintf(out,"%d\n",sum[b]-sum[a-1]);
}
return 0;
}
The programs below gets n integers from 1 to m and sorts them. Again, I cannot calculate the time complexity.
[input sample]
5 5
2 1 3 4 5
[output sample]
1 2 3 4 5
Program:
#include <stdio.h>
FILE *in=fopen("input.txt","r")
FILE *out=fopen("output.txt","w")
int n,m;
int data[1000];
int count[1000];
int main()
{
int i,j;
fscanf(in,"%d%d",&n,&m);
for(i=0;i<n;i++)
{
fscanf(in,"%d",&data[i]);
count[data[i]]++
}
for(i=1;i<=m;i++)
{
for(j=0;j<count[i];j++) fprintf(out,"%d ",i);
}
return 0;
}
It's ironic(or not) that I cannot calculate the time complexity of my own algorithms, but I have passions to learn, so please programming gurus, help me!
