title: Bubble sort worst case example is O(n*n), how?
body: <p>I am trying Bubble sort. There are 5 elements and array is unsorted. Worst case for bubble sort shuold be O(n^2).</p>
  
  <p>As an exmaple I am using </p>
  
  <p>A = {5, 4, 3, 2, 1}</p>
  
  <p>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</p>
  
  <pre><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 &lt; (A.Length - 1); i++)
                  {
                      count++;
                      if(A[i] &gt; A[i+1])
                      {
                          temp = A[i];
                          A[i] = A[i+1];
                          A[i+1] = temp;
                          sorted = false;
                      }
  
                      Console.Write(count + ". -&gt; ");
                      for(int k=0; k&lt; 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();
      }
     } 
    }
  </code></pre>
  
  <p>Output is following</p>
  
  <ol>
  <li>-> 45321</li>
  <li>-> 43521</li>
  <li>-> 43251</li>
  <li>-> 43215</li>
  <li>-> 34215</li>
  <li>-> 32415</li>
  <li>-> 32145</li>
  <li>-> 32145</li>
  <li>-> 23145</li>
  <li>-> 21345</li>
  <li>-> 21345</li>
  <li>-> 21345</li>
  <li>-> 12345</li>
  <li>-> 12345</li>
  <li>-> 12345</li>
  <li>-> 12345</li>
  <li>-> 12345</li>
  <li>-> 12345</li>
  <li>-> 12345</li>
  <li>-> 12345</li>
  </ol>
  
  <p>Any idea why the maths its not coming out to be 25?</p>