Which code has a higher cost? (Bubblesort in C)

Question

Which code has a higher cost? (Bubblesort in C)

Navigation

#1 by (2 votes)

1

void bubblesort(int *A, int n) {
    int i, aux;
    for(i=0; i<n-1; i++){
        if(A[i]>A[i+1]){
            aux = A[i];
            A[i] = A[i+1];
            A[i+1] = aux;
        }
    }
    if(n-1>1)
        bubblesort(A, n-1);
}
void bubblesortI(int *A, int n) {
    int i, aux, j; 
    int troca=0;                //1
    for(i=0; i<n-1; i++){       //Pìor C. = 2n          Melhor C. = 1;
        for(j=0;j<n-i-1; j++){  //Pior C. = n²+n-2      Melhor C. = 2n
            if(A[j]>A[j+1]){    //Pior C. = (n²+n)/2    Melhor C. = n-1
                aux = A[j];     //Pior C. = (n²+n)/2    Melhor C. = 0
                A[j] = A[j+1];  //Pior C. = (n²+n)/2    Melhor C. = 0
                A[j+1] = aux;   //Pior C. = (n²+n)/2    Melhor C. = 0
                troca =1;       //Pior C. = (n²+n)/2    Melhor C. = 0
            }
        }
        if(!troca)              //Pior C. = n-1         Melhor C. = 1;
            break;
    }
    //Pior caso: O(n²)  Melhor caso: O(n)
}

I am studying ordering and complexity and I ended up doing the recursive and iterative bubblesort code and wanted to define the order of them, but I can not figure out how to calculate the complexity of recursive codes.

In front of the iterative code is the cost of each line.

PS: If someone has a costing and complexity calculation tool for recursive algorithms, I'll be happy.

c

asked by anonymous 15.01.2018 / 18:46

1 answer

Get SRC value from Source tag with JS Catch the value of an input and return alert

score 2 · Accepted Answer

In the iterative case, you calculated correctly.

From what I understand in the comments, you want to assess the asymptotic complexity of your algorithms. The analysis of asymptotic complexity deals only with the algorithm and not with the specific details of the language where the algorithm is implemented. In fact, if we are to consider everything, we would also have to take into account the operating system, the hardware and more n other factors that weigh in the calculation of the cost of your code. To avoid this fatigue, asymptotic analysis deals only with the number of times that each line of code will be executed, and in the end we consider only the highest degree factor (in the case of bubblesort it is n² ). If you want to know more about this, you can search for the Big-O notation on Google.

It is easy to calculate the asymptotic complexity of an iterative algorithm, but in the case of recursive algorithms, you will have to deduce what your complexity will be through a numerical analysis. Considering your algorithm:

void bubblesort(int *A, int n) {
    1 int i, aux;
    2 for(i=0; i<n-1; i++){
    3     if(A[i]>A[i+1]){
    4       aux = A[i];
    5       A[i] = A[i+1];
    6       A[i+1] = aux;
    7   }
    8 }
    9 if(n-1>1)
   10     bubblesort(A, n-1);
}

On a first look, we have already seen that the for loop line will always be called n-1 times. Consequently, all code that is within that loop will also be subject to execution n-1 times. Because there is no other nested loop and no other function call or code interrupt worth taking into account, the complexity of this code snippet (lines 2 through 6) is O (n) .
Already for the recursive call, you will need to analyze the stop condition in conjunction with the next call. If we decrease the n every time we call the function recursively, and if the stop condition causes the program to end when n-1>1 (or, rewriting, n > 2 ), then we know that the function will be called n - 2 times . Again, we'll only consider the n .
In total, the complexity of your code is O (n²) , taking into account the loopback and recursive calls.

If we're going to look at another code:

int funcaoRecursiva(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + funcaoRecursiva(n/2);
}

The complexity of this code is O (log n) . Because? Because the function stops when n <= 0 , and n is divided by two for each recursive call. That is, the function follows the time of f(n) = n/2 , which is a simple example of logarithmic function in base 2.

I hope to have helped clarify your question.