Time Complexity of the Algorithms

Question

I have created two algorithms that calculate the prefix averages with a given array. I wanted to derive the time complexities of both algorithms, but I have been struggling a bit. I watched this YouTube video: https://www.youtube.com/watch?v=udwxWq9wZgg&safe=active. I did not understand how to count the operations in a for loop and a nested for loop.

At 2:27, I managed to count the operations in the for loop in PrefixAverages2. It was 3n+1. However, I cannot understand from 5:50 onwards.

Thanks in advance.

public double[] PrefixAverages1(double input[])
{
    double A[] = new double[input.length];
    double s;


    for(int i=0; i <= input.length - 1 ;i++)
    {
        s = input[0];

        for(int j=1; j <= i ;j++)
        {
            s = s + input[j];
        }

        A[i] = s / (i+1);
    }


    return A;  

}





public double[] PrefixAverages2(double input[])
{
    double A[] = new double[input.length];
    double s = 0;

    for( int i=0; i <= input.length - 1 ; i++)
    {
        s = s + input[i];
        A[i] = s / (i+1);

    }

    return A;  

}

Check those questions, they might help you: [first](http://stackoverflow.com/questions/487258/) / [second](http://stackoverflow.com/questions/3255/). — Laf, Oct 15 '15 at 19:41
And the question is where? Anyhow the second one is trivial, and the former is just summing up all integers from 1 to `input.length` - the closed formula for that is n*(n+1)/2 — Voo, Oct 15 '15 at 19:41
so counting the operations of the first algorithm: 1 + n*(n+1)/2 + 2 + 1 which is n*(n+1)/2 + 4 — Rob Neal, Oct 15 '15 at 20:05

score 1 · Answer 1 · answered Oct 15 '15 at 19:43

1

   for(int i=0; i <= input.length - 1 ;i++)
        for(int j=1; j <= i ;j++)

This is quadratic, for a given i, inner loop goes about i-times, so you have to sum over i, so basically you have something like sum_{i=1}^{i=l} i, which is the sum of the first l integers, so l(l+1)/2, then quadratic.

For the second algorithm you just have one loop so its complexity is linear.

answered Oct 15 '15 at 19:43

Jean-Baptiste Yunès

34,548
4
48
69

1st line: 3n+1 2nd line: 3n+1 so 9n^2+2? – Rob Neal Oct 15 '15 at 19:52
(first algo) You have : i=0 -> 0 times in inner loop, i=1 -> 1 time in inner loop, i=2 -> 2 times in inner loop, i=3 -> 3 times in inner loop, so 0+1+2+3... up to length-1... So exactly length(length-1)/2. In the second algo you just go from 0 to length-1, so length times the content of the loop, linear. You have to count the number of times the content of a given loop is executed... – Jean-Baptiste Yunès Oct 15 '15 at 19:56

Time Complexity of the Algorithms

1 Answers1