Bubble sort worst case example is O(n*n), how?

Question

I am trying Bubble sort. There are 5 elements and array is unsorted. Worst case for bubble sort shuold be O(n^2).

As an exmaple I am using

A = {5, 4, 3, 2, 1}

In this case the comparison should be 5^2 = 25. Using manual verification and code, I am getting comparison count to be 20. Following is the bubble sort implemenation code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SortingAlgo
{
class Program
{
    public static int[] bubbleSort(int[] A)
    {
        bool sorted = false;
        int temp;
        int count = 0;
        int j = 0;
            while (!sorted)
            {
                j++;
                sorted = true;
                for (int i = 0; i < (A.Length - 1); i++)
                {
                    count++;
                    if(A[i] > A[i+1])
                    {
                        temp = A[i];
                        A[i] = A[i+1];
                        A[i+1] = temp;
                        sorted = false;
                    }

                    Console.Write(count + ". -> ");
                    for(int k=0; k< A.Length; k++)
                    {
                        Console.Write(A[k]);
                    }
                    Console.Write("\n");

                }                
            }
      return A;

    }

    static void Main(string[] args)
    {
        int[] A = {5, 4, 3, 2, 1};
        int[] B = bubbleSort(A);
        Console.ReadKey();
    }
   } 
  }

Output is following

1. -> 45321
2. -> 43521
3. -> 43251
4. -> 43215
5. -> 34215
6. -> 32415
7. -> 32145
8. -> 32145
9. -> 23145
10. -> 21345
11. -> 21345
12. -> 21345
13. -> 12345
14. -> 12345
15. -> 12345
16. -> 12345
17. -> 12345
18. -> 12345
19. -> 12345
20. -> 12345

Any idea why the maths its not coming out to be 25?

Answer 1

Remember that O(N^2) is simplified from the actual expression of C * N(2); that is, there is a bounded constant. For bubble sort, for example, C would be roughly 1/2 (not exactly, but close).

Your comparison count is off too, I think, it should be 10 pairwise comparisons. But I guess you could consider swapping of elements to be another. Either way, all that does is change the constant, not the more important part.

Answer 2

Big-O notation doesn't tell you anything about how many iterations (or how long) an algorithm will take. It is an indication of the growth rate of a function as the number of elements increases (usually towards infinity).

So, in your case, O(n²) simply means that the bubble sort's computational resources grows by the square as the number of elements. So, if you have twice as many elements, you can expect it to take (worst case) 4-times as long (as an upper bound). If you have 4-times as many elements, the complexity increases by a factor of 16. Etc.

For an algorithm with O(n²) complexity, five elements could take 25 iterations, or 25,000 iterations. There's no way to tell without analyzing the algorithm. In the same vein, a function with O(1) complexity (constant time) could take 0.000001 seconds to execute or two weeks to execute.

Answer 3

If an algorithm takes n^2 - n operations, that's still simplified to O(n^2). Big-O notation is only an approximation of how the algorithm scales, not an exact measurement of how many operations it will need for a specific input.

Answer 4

Consider: Your example, bubble-sorting 5 elements, takes 5x4 = 20 comparisons. That generalizes to bubble-sorting N elements takes N x (N-1) = N^2 - N comparisons, and N^2 very quickly gets a LOT bigger than N. That's where O(N^2) comes from. (For example, for 20 elements, you are looking at 380 comparisons.)

Answer 5

Bubble sort is a specific case, and its full complexity is (n*(n-1)) - which gives you the correct number: 5 elements leads to 5*(5-1) operations, which is 20, and is what you found in the worst case.

The simplified Big O notation, however, removes the constants and the least significantly growing terms, and just gives O(n^2). This makes it easy to compare it to other implementations and algorithms which may not have exactly (n*(n-1)), but when simplified show how the work increases with greater input.

It's much easier to compare the Big O notation, and for large datasets the constants and lesser terms are negligible.