# What is the recurrence form of Bubble-Sort

I understand how bubble sort works and why it is O(n^2) conceptually but I would like to do a proof of this for a paper using the master theorem.

As an example: The recurrence form for merge sort is T(n) = 2T(n/2) + O(n) which, using the master theorem, gives us O(n log(n)).

I am unsure of how to do this process with Bubble sort. What equation allows us to see that it is O(n^2)?

• The Master theorem is used to estimate the upper bound for divide-and-conquer recurrences. The Bubble sort per se does not produce a recursive relation, so I don't see any point in using the Master theorem for the Bubble sort analysis. – fade2black Nov 19 '17 at 23:18
• Not sure why people are voting to close as unclear. A question isn't unclear just because the answer turns out to be, "Sorry but you can't do that." – David Richerby Nov 20 '17 at 11:00

Bubble sort uses the so-called "decrease-by-one" technique, a kind of divide-and-conquer. Its recurrence can be written as

$$T(n) = T(n-1) + (n-1).$$

• I can readily see how decrease-by-one approach is applicable to Insertion sort but how is it so for Bubble sort? What is the measure of performance here? @fade2black – LastIronStar Nov 20 '17 at 8:09

As user fade2black points out in their comment, Bubble Sort is not an algorithm that employs the typical divide-and-conquer strategy to solve the problem of sorting. Having said that, let us now derive the running time of Bubble Sort. Before that, let's look at the algorithm itself:

Input: An array $A[1,\cdots,n]$
Output: array $A$ sorted in order of non-decreasing elements.

$\mathsf{BubbleSort(A)}$:
$\quad n = A.length$
$\quad \mathsf{for}\ i = 1\ \mathsf{to}\ n$
$\qquad \mathsf{for}\ j = 1\ \mathsf{to}\ n-i$
$\qquad \quad \mathsf{if(}A[j]>A[j+1]\mathsf{)}$
$\qquad \qquad \mathsf{swap(}A[j],A[j+1]\mathsf{)}$
$\mathsf{END}$

Now firstly, if we measure running time as the number of comparisons performed by $\mathsf{BubbleSort}$, then we observe that for each iteration of loop variable $i$, there are $n-i$ comparisons being made. Thus, total number of comparisons performed is: $\sum_{i=1}^nn-i = \frac{n(n-1)}{2} \in \Theta(n^2)$

Suppose instead of measuring performance/running time by number of comparisons, we want to do so by the number of $\mathsf{swap(x,y)}$ operations performed. It is difficult to estimate the average running time as measured in number of $\mathsf{swap}$ operations without making assumptions on the nature of distribution of the input set.

However, it is fairly simple if our interest is in the worst case performance - for any input size $n$, we try to choose the array $A$ that maximises the number of swaps. Clearly, we can't have more $\mathsf{swap}$ operations performed than the number of comparisons we make(convince yourself of this).

Thus, total number of $\mathsf{swap}$ operations required by a run of $\mathsf{BubbleSort}$ is $\leq \frac{n(n-1)}{2}$.

Now all that remains is to show that this is a tight bound and to do so, consider input of the form $A = [n,n-1,\cdots,1]$ i.e., in the input $A[i]=n-i+1$. It is easy to verify that this particular input requires exactly $\frac{n(n-1)}{2}\ \mathsf{swap}$ operations to produce the output. Thus, in the worst case, running time of $\mathsf{BubbleSort}$ measured in terms of $\mathsf{swap}$ performed is $\frac{n(n-1)}{2} \in \Theta(n^2)$.

In otherwords, agnostic to exact input, running time is $O(n^2)$