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

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 2

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.