Time complexity of a sorting algorithm

Posted by Passonate Learner on Stack Overflow See other posts from Stack Overflow or by Passonate Learner
Published on 2010-04-11T11:48:26Z Indexed on 2010/04/11 11:53 UTC
Read the original article Hit count: 541

Filed under:
|

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!

© Stack Overflow or respective owner

Related posts about c++

Related posts about time-complexity