CODEWITHSUNDEEP
complexity-theorysortingbubble-sort
OneTwo12
OneTwo12

Reputation: 21

Why Bubble sort complexity is O(n^2)?

As I understand, the complexity of an algorithm is a maximum number of operations performed while sorting. So, the complexity of Bubble sort should be a sum of arithmmetic progression (from 1 to n-1), not n^2. The following implementation counts number of comparisons:

public int[] sort(int[] a) {
    int operationsCount = 0;
    for (int i = 0; i < a.length; i++) {
        for(int j = i + 1; j < a.length; j++) {
            operationsCount++;
            if (a[i] > a[j]) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    System.out.println(operationsCount);
    return a;
}

The ouput for array with 10 elements is 45, so it's a sum of arithmetic progression from 1 to 9.

So why Bubble sort's complexity is n^2, not S(n-1) ?

Upvotes: 2

Views: 7128

Answers (3)

Vivek Singh
Vivek Singh

Reputation: 1025

Worst case scenario: indicates the longest running time performed by an algorithm given any input of size n

so we will consider the completely backward list for this worst-case scenario

int[] arr= new int[]{9,6,5,3,2};

Number of iteration or for loops required to completely sort it  = n-1 //n - number of elements in the list

1st iteration requires (n-1) swapping + 2nd iteration requires (n-2) swapping + ……….. + (n-1)th iteration requires (n-(n-1)) swapping

i.e. (n-1) + (n-2) + ……….. +1 = n/2(a+l) //sum of AP
=n/2((n-1)+1)=n^2/2

so big O notation = O(n^2)

Upvotes: 0

Daniel Mart&#237;n
Daniel Mart&#237;n

Reputation: 7845

Let's do a worst case analysis.

In the worst case, the if (a[i] > a[j]) test will always be true, so the next 3 lines of code will be executed in each loop step. The inner loop goes from j=i+1 to n-1, so it will execute Sum_{j=i+1}^{n-1}{k} elementary operations (where k is a constant number of operations that involve the creation of the temp variable, array indexing, and value copying). If you solve the summation, it gives a number of elementary operations that is equal to k(n-i-1). The external loop will repeat this k(n-i-1) elementary operations from i=0 to i=n-1 (ie. Sum_{i=0}^{n-1}{k(n-i-1)}). So, again, if you solve the summation you see that the final number of elementary operations is proportional to n^2. The algorithm is quadratic in the worst case.

As you are incrementing the variable operationsCount before running any code in the inner loop, we can say that k (the number of elementary operations executed inside the inner loop) in our previous analysis is 1. So, solving Sum_{i=0}^{n-1}{n-i-1} gives n^2/2 - n/2, and substituting n with 10 gives a final result of 45, just the same result that you got by running the code.

Upvotes: 0

paddy
paddy

Reputation: 63471

This is because big-O notation describes the nature of the algorithm. The major term in the expansion (n-1) * (n-2) / 2 is n^2. And so as n increases all other terms become insignificant.

You are welcome to describe it more precisely, but for all intents and purposes the algorithm exhibits behaviour that is of the order n^2. That means if you graph the time complexity against n, you will see a parabolic growth curve.

Upvotes: 8

Related Questions