Time consumption in cubic code

Asked

Viewed 80 times

1

I need to calculate the time consumption of the following algorithm:

int somaSequencial(int v[],int n){
    int m = 0;
    for(int i = 0; i < n; i++){
        for(int j = i; j < n; j++){
            int s = 0;
            for(int k = i; k <= j; k++){
                s+= v[k];
            }
            if(s > m){
                m = s;
            }
        }
    }
    return m;
}

After naming each operation, from t1 to T15, I came to the following conclusion:

F(n) = a + b(n) + c(n/2)(n+1) + d[ "Sum from i=1 to n" (n/2)(n+1)]

I would like to know if it is correct, since it is a cubic algorithm.

java
  • 2

    It has a very simple method to evaluate the behavior of this function. Remove the variables m and s, declare at first passosLoop3 = 0 and passosLoop2 = 0. Instead of making the sum in s, do passosLoop3++. In place of if, do passosLoop2++. Test for some controlled values of n and make the polynomial interpolation that meets the passosLoop3 and passosLoop2

  • 1

    @Jeffersonquesado You can even enter the numbers on that website there, what he does to it for himself. Apparently this is something like x^3/6+x^2/2+x/3

  • @Brunocosta interesting the site, I will analyze more calmly after leaving work

  • Bruno Costa, how to use this site?

1 answer

3


I followed the idea of @Jefferson Quesado. You can get the complexity of your algorithm by incrementing a counter. Basically Voce only needs to know the total number of iterations for each value of n.

function somaSequencial(v, n){
    var total = 0;
    for(var i = 0; i < n; i++){
        for(var j = i; j < n; j++){
            for(var k = i; k <= j; k++){
                total++;
            }
        }
    }
    return total;
}

for(var i = 0; i < 8; ++i){
    console.log("(" + i + ", " + somaSequencial([1, 2, 3, 4, 5, 6, 7, 8], i) + ")");
}

As you can see the output is as follows: (0, 0) (1, 1) (2, 4) (3, 10) (4, 20) (5, 35) (6, 56) (7, 84)

Now you can do the interpolação polinomial to get the formula. I used this site. You just have to take the output and put it in the text box and you will get the following result

f(x) = x^3 / 6 + x^2 / 2 + x / 3
  • 1

    This approach ignores the if. If you want to count if You will have to have another counter. Do the same process and do the sum of the functions. But it is clear what degree of function will not increase. So the function belongs to O(n^3)

Browser other questions tagged java

You are not signed in. Login or sign up in order to post.