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 */
     /* From the first element to the end
       of the unsorted section */
        /* If adjacent items are out of order, swap them */
       if( a[j-1]>a[j] ) SWAP(a[j-1],a[j]);
  • 6
    $\begingroup$ Bubble sort is a classic algorithm, a quick google will give you the information you're after. $\endgroup$ Oct 7, 2012 at 10:18
  • 4
    $\begingroup$ I am tempted to close this question. Blurping code (C, no less!) here and not even taking the time to write down a proper question is not how Stack Exchange should be used. Please include your own effort. You also need to state which operations should be counted. $\endgroup$
    – Raphael
    Oct 7, 2012 at 15:48
  • $\begingroup$ See here and here for similar analyses. $\endgroup$
    – Raphael
    Oct 7, 2012 at 15:51
  • $\begingroup$ It's been documented and provable that no matter what what kinds of optimization, bubblesort is always O(n^2). $\endgroup$
    – CS2016
    Oct 11, 2017 at 13:56

1 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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.