CODEWITHSUNDEEP
sortingbig-ocomplexity-theory
Guilherme Neves
Guilherme Neves

Reputation: 33

What is the worst-case asymptotic cost of this algorithm?

void Ordena(TipoItem *A, int n)
{

    TipoItem x;

    int i, j;

    for (i = 1; i < n; i++)
    {

        for (j = n; j > i; j--)
        {

            if (A[j].chave < A[j - 1].chave)
            {

                x = A[j];

                A[j] = A[j - 1];

                A[j - 1] = x;
            }
        }
    }

}

I believe the worst case is when the array is in descending order, am I right? About the asymptotic cost in terms of number of movements, is it O(n²) or O(2n²) ? I've just started learning about asymptotic cost (as you can tell).

Upvotes: 0

Views: 55

Answers (1)

Taras Rashkevych
Taras Rashkevych

Reputation: 26

As you were saying the worst-case scenario here is the one where the array is in descending order because you will have to execute the if statement every single time. However, since we are talking about the asymptotic notation, it is quite irrelevant whether or not you execute the if statement because the cost of those three instructions is actually constant(i.d. O(1)). Therefore, the important thing here is how many times you actually have to loop through the elements in the array and this happens exactly, if you do the math, n^2/2 + n/2 times. So, the computational complexity is O(n^2) because the predominant part here is n^2/2, and the asymptotic notation doesn't take into account the multiplicative factor 1/2, even if sometimes these factors could influence the execution time.

Upvotes: 1

Related Questions