Time complexity of a sorting algorithm

Question

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!

Answer 1

What you need to do is pay attention to the loops, specifically how many times the loops repeat, and how much time is spent inside the loops. You need to multiple the number of times the outer loop repeats by the amount of time it takes inside the loop... if there is a inner loop, you multiply the number of repititions of the outer loop by the number of repititions of the inner loop, for example, to get the time complexity.

In your first program, you have one loop that takes O(n) time followed by a loop that takes O(q*(b-a)) time... it isn't exactly clear to me what b and a represent... but if you can bound b-a (let's say, you know that b-a < n), then you can express this more simply (e.g. if b-a < n, then you would say it was O(q*n)). The overall runtime would be the sum of those two terms, or, if one term is always bigger than the other, use the bigger term.

In the second program, you have two loops, each taking O(n) time, followed by a loop that takes O(q) time. So, the overall runtime is O(n+q). Note that if one term dominates the other, you can drop the term that is smaller. Even without knowing the value of (b-a), it is already apparent that this is better than the first one.

In the third program, the overall runtime is O(n+m), because you have one loop that takes O(n) time followed by a loop that takes O(m) time. If you know that m < n or vice-versa, you can simplify the expression by dropping the dominating term. If they can vary so that you don't know that one dominates the other, then writing it out as O(m+n) is the best you can do in terms of stating the time-complexity.

I should also point out that even if a loop is performed more than once, but it is performed a fixed number of times (e.g. in program 2, you have two loops that take O(n) time), it doesn't affect the time-complexity, because O(2n) is the same as O(n); in other words, constant factors don't matter in big-Oh complexity analysis. Also, if you have an inner loop that varies in terms of the number of times it is executed, if you are performing "worst-case" complexity analysis, you only need to know the worst possible value it can have.

For example, consider the following loop:

for (int i = 0; i < n; i++ ){
   for (int j = i+1; j < n; j++ ){
       // something taking O(1) time
   }
}

The loop above takes O(n^2) time, even though not all the inner loops will take O(n) time.

I would also like to add that you should do a better job of formatting your program. Even though braces are not strictly required when an if/for/while statement only has one statement in the body, it is much more readable to use the braces anyway, and to use a newline. For example, it is much more readable if you write:

for (int i=1; i<=n; i++) {
    sum[i]=sum[i-1]+data[i];
}

Than writing it as for (i=1; i<=n; i++) sum[i]=sum[i-1]+data[i];. Also, I should point out that even though you have tagged this question as C++, you are using C-like code... in C++, you can declare variables in the initialization of the for-loop (I suggest you do so). Also, in C++, the iostreams library (std::cin, std::cout, std::fstream, std::ostringstream, std::istringstream, etc.) are preferred over C FILE* objects.

You may also be interested in the following resource:

• Stanford University: Analysis of Algorithms from Google Code University