I don't understand how the worst case performance of bubble sort is O(n^2)

Question

The course materials say the worst case of bubble sort is O(n²) – when every item in the list is in the worst possible position. I'm having trouble wrapping my mind around this.

If I have a list of 5 numbers – 5, 4, 3, 2, 1 – and I want them to be sorted in ascending order, they would be in the worst possible position. If I go through each of the swaps it would look like this:

5 4 3 2 1

4 5 3 2 1

4 3 5 2 1

4 3 2 5 1

4 3 2 1 5

3 4 2 1 5

3 2 4 1 5

3 2 1 4 5

2 3 1 4 5

2 1 3 4 5

1 2 3 4 5

This is not 25 swaps. So why is bubble sort said to be O(n²)?

Answer 1

Well, the number of iterations you did was basically

n + (n - 1) + (n - 2) + ... + 1

Mathematically, this is equal to n (n + 1) / 2 which is equal to n^2 + n / 2 and since we don't care about small numbers (n / 2) in this case, we can ignore it (if n = 1000, n^2 = 1,000,000 while n/2 = 500 which is not a big deal). So we can say it's a O(n^2) algorithm.

Answer 2

Bubble sort is one of the easiest sorting technique from the point of view of implementation, but the one of the worst to get into practical use. It has best, worst (, and hence average) case all equal to O(n^2).

Lets see how? This pseudocode is copied from Wikipedia (and I made little modifications in it). For this question I am not dealing with the optimized code mentioned there, but believe me, that too runs in O(n^2). This code will arrange the elements in ascending order.

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat 
        for i = 0 to n-2 inclusive do
           /* if this pair is out of order */
           if A[i] > A[i + 1] then
               /* swap them and remember something changed */
               swap( A[i-1], A[i] )
           end if
        end for
     until not swapped
end procedure

In Bubble Sort, firstly, We scan the list elements from starting to the second last element. During the scan, we compare the ith element with the i+1th element(i.e. the element next to it). If ith element is greater than its next element, then we swap them(swapping takes constant time, not linear). So during the first scan, we have ran into n-1 operations(or unit jobs), And we have sorted the list, right?

Actually no. You took the largest element in the list to its correct position but we can't say anything about the rest of the elements. So we do the same thing again, scan it in the same way. Then after second scan, we would have taken the second largest element of the list to its correct position. And we keep on repeating this strategy n-1 times, as that would make sure that we have got n-1 elements at their desired position in the list. Now since we have ran a strategy n-1 times (the strategy that itself takes n-1 time units), then the total time taken should be

  (n-1)*(n-1)
= n*n + 1 - 2*n    // considering part that effects the most
= n*n

And so, Bubble Sort takes O(n^2) time.

Let us consider the list you mentioned, 5 4 3 2 1, lets sort it.

5 4 3 2 1

4 5 3 2 1
4 3 5 2 1
4 3 2 5 1
4 3 2 1 5

3 4 2 1 5
3 2 4 1 5
3 2 1 4 5
3 2 1 4 5

2 3 1 4 5
2 1 3 4 5
2 1 3 4 5
2 1 3 4 5

1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5

And that makes up to 16 steps which is exactly equal to (n-1)^2(and that's not 5^2 = 25!). The thing that you should note, is that if any algorithm runs in O(n^2), that does not literally mean that you go on squaring the input size. No algorithm could have been directly written in its exact form(n^2 or n*log(n) or ...) because the implementations vary from programmer to programmer, but the sole complexity remains the same(here n*n).

For example, consider above equation (n-1)*(n-1). Now let me add that swapping itself took k units of time, then our equation would have been

(n-1)*(n-1 + (k)) = (n-1)*(n+k-1) = n*n + (k - 2)*n - k + 1

Ofc, considering the part of the equation which effects it the most, we again land on n^2, no matter how one implements swap()!!!(unless constant time).

For any of your implementation of any algorithm (say of n^2), you can figure out exact number of steps in a similar way, that would result in form of

f(n) = a*n^2 + b*n + c

Putting correct values of a, b, c, you can get exact number of steps that your own implementation takes for a particular input. But when you tell someone the complexity of your code, then it means you need to tell the part of f(n) that has the most weight-age in that equation.

Good Luck.

---

P.S. :

1. Consider ^ to be exponentiation and not XOR.

2. Consider list and arrays to be same for now.

Answer 3

The Landau-Notation Big O considers the asymptotic runtime, since that doesn´t help you, that means: You are right n2 isn´t the real runtime, it is (n*n-1) / 2. But if you consider that n is a real real big number, tending to infinity, factors or divisors of n just doesn´t matter anymore, so in the Big O notation you don´t mention them anymore.

Answer 4

If we actually count the number of iterations, then for n = 5, the total number of iterations is 10. Take a bubble sort implementation in java as for arr = [5,4,3,2,1]

 for(int j=arr.length-1; j > 0; j--){
        for(int i = 0; i<j;i++){

            if(arr[i] > arr[i+1]){
                swap(arr,i,i+1); //does swapping
            }
        }
    }

The above code iterates for j = {(0,1,2,3) + (0,1,2) + (0,1) + (0)} which is equal to 10 and which is equal to 5*(5-1)/2.

Hence, T(bubbleSort) = n*(n-1)/2 -> (n^2)/2 - ((n-1)^2)/2. This is the real equation.

Big(O) is for representing the progression not the actual value which is obtained by the order of the equation or the first term in the equation which is for above case n^2.