Complexity of optimized bubblesort [closed]

Question

What is the runtime complexity of the following implementation of Bubblesort (for integers)?

    #define SWAP(a,b)   { int t; t=a; a=b; b=t; }

    void bubble( int a[], int n )
    /* Pre-condition: a contains n items to be sorted */
    {
       int i, j;
      /* Make n passes through the array */
      for(i=0;i<n-1;i++)
      {
     /* From the first element to the end
       of the unsorted section */
        for(j=1;j<(n-i);j++)
        {
        /* If adjacent items are out of order, swap them */
       if( a[j-1]>a[j] ) SWAP(a[j-1],a[j]);
       }
    }
}  

Answer 1

The first iteration will do will do $n-1$ comparisons, the next $n-2$, the second $n-3$ and so on. In total $n-1$ iterations are done.

Hence, you need to find the sum of $(n-1)+(n-2) + ... + 1$ which is $((n-1)^2+n-1)/2$ which still is $O(n^2)$. So the optimization does not improve the asymptotic running time.

Note that I edited your algorithm slightly: the outer loop is only iterated $n-1$ times. This is because for each iteration, one more element is put into the right place. Hence after $n-1$ iterations, $n-1$ elements will be in the right place and so element $n$ must also be in the right place.