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