Which code has the highest cost? (Bubblesort in C)

Question

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’m studying ordering and complexity and ended up doing the recursive and iterative bubblesort code and wanted to define their order, only I can’t understand 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 recursive algorithm complexity and cost calculation tip, I’ll be happy.

Answer 1

In the iterative case, you calculated correctly.

From what I understand in the comments, you want to evaluate the asymptotic complexity of your algorithms. Asymptotic complexity analysis deals only with the algorithm and not with the language-specific details where the algorithm is implemented. In fact, if we were to consider everything, we would also have to take into account the operating system, hardware and more n other factors that weigh in the calculation of the cost of your code.

To avoid this fatigue, the asymptotic analysis deals only with the amount of times each line of the code will be executed, and at the end we consider only the factor of the highest degree (in the case of bubblesort is the n²). If you want to know more about this, you can search on the notation Big-O 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 will be its complexity 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);
}

• At first glance, we have already found that the loop line for will always be called n-1 times. Consequently, any code within that loop will also be subject to execution n-1 times. Since 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 to 6) is O(n).
• For the recursive call, you will need to analyze the stop condition in conjunction with the next call. If we decrease the n each 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 will take into consideration only the n.
• In total, the complexity of your code is O(n²), taking into account the repetition loop and recursive calls.

If we go to analyze 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). Why? Because the function stops when n <= 0, and n is divided by two at 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 I’ve helped clear up your doubt.