Temporal complexity of the sorting algorithm

Question

The two programs below get n integers from the file and calculate the sum of to to bth integers q (number of questions). I think the top program has worse time complexity than the lower one, but I am 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 get n integers from 1 to m and sort them. Again, I cannot calculate the complexity of time.

 [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 is ironic (or not) that I cannot calculate the time complexity of my own algorithms, but I have passions to learn, so please program the gurus, help me!

Answer 1

What you need to do is pay attention to the loops, in particular how many times the loops repeat and how much time is spent inside the loops. You need to multiply the number of repetitions of the outer loop by the amount of time it takes inside the loop ... if there is an inner loop, you multiply the number of repetitions of the outer loop by the number of repetitions 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 * (ba)) time ... it's not entirely clear to me what b and a represent ... but if you can bind ba (let's say you know that ba <n), then you can express it more simply (for example, if ba <n, then you would say that it is O (q * n)), Total duration fulfillment will be the sum of these two terms, or, if one term is always larger than the other, use the larger term.

In the second program, you have two loops, each of which takes O (n) time, and then a loop that takes O (q) time. Thus, the total execution time is O (n + q). Please note that if one member dominates the other, you can refuse the smaller one. Even without knowing the meaning of (ba), it is already obvious that this is better than the first.

In the third program, the total execution time is O (n + m), because you have one cycle that takes O (n) time, followed by a cycle that takes O (m) time. If you know that m <n or vice versa, you can simplify the expression by dropping the dominant term. If they can change so that you don’t know that one dominates the other, then writing it as O (m + n) is the best thing you can do in terms of time complexity.

I should also point out that even if the cycle is executed several times, but is executed a fixed number of times (for example, in program 2, you have two loops that take O (n)), t affects the time complexity, since O (2n ) coincides with O (n); in other words, constant factors are not of great importance in the analysis of complexity with a high degree of complexity. Also, if you have an inner loop that varies depending on the number of times it runs, if you are doing a worst case complexity analysis, you only need to know the worst possible value that 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, although not all inner loops will take O (n) time.

I would also add that you should better format your program. Despite the fact that curly braces are not strictly required if the if / for / while statement has only one statement in the body, it is much more convenient to use curly braces and use a new line. For example, this is more readable if you write:

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

How to write it as for (i=1; i<=n; i++) sum[i]=sum[i-1]+data[i]; . In addition, I must point out that although you marked this question as C ++, you use C-like code ... in C ++, you can declare variables in a for-loop initialization (I suggest you do this). In addition, in C ++, the iostreams library ( std :: cin , std :: cout , std :: fstream , std :: ostringstream , std :: istringstream , etc.) is preferable to C FILE * objects.

You may also be interested in the following resource:

• Stanford University: Algorithm Analysis from Google Code University