2
$\begingroup$

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)?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – fade2black Nov 19 '17 at 23:18
  • 1
    $\begingroup$ 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." $\endgroup$ – David Richerby Nov 20 '17 at 11:00
4
$\begingroup$

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).$$

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – LastIronStar Nov 20 '17 at 8:09
2
$\begingroup$

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)$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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