# Why does bubble sort do $\Theta(n^2)$ comparisons on an $n$ element list?

I have a quick question on the bubble sort algorithm. Why does it perform $\Theta(n^2)$ comparisons on an $n$ element list?

I looked at the Wikipedia page and it does not seem to tell me. I know that because of its magnitude it takes a lot of work with large numbers.

• this notation is not strictly correct; $\Theta(\cdot)$ is also a lower bound, and bubble sort can do fewer comparisons depending on the initial ordering. it is $O(n^2)$ in worst case. – vzn Feb 4 '14 at 0:01

## 2 Answers

Consider the worst case analysis: when the array is completely sorted, but from largest to smallest. In this case, bubble sort will make $n-i$ swaps in iteration $i$ (and in particular, there will be a swap in every iteration), and repeat that for $n-1$ times. This gives a total runtime of $(n-1)^2=\Theta(n^2)$.

Observe that even under some optimizations of the naive bubble sort, the runtime is still ${n\choose 2}=\theta(n^2)$.

• Like what vzn said, this is incorrect. It is indeed in $O(n^2)$, but it is in $\Omega (n)$, because of the best case when the elements are already sorted. Since the lower bound and upper bound are not equivalent, it is wrong to say $\Theta(n^2)$. – Curious Feb 27 '14 at 12:14

I have to disagree slightly with what Shaull said, although it still comes out to the same big-theta run time. It is true that the first element in a reversely sorted list will have n-1 comparisons, but each suqsequent element will have one less. Leading to $\sum_{i=o}^{n-1} i = \frac{n(n-1)}{2}$ number of comparisons, which still comes out to $\Theta(n^2)$ number of comparisons.

• This is what I meant by "some optimization". The (ridiculously) naive bubble-sort doesn't utilize this fact, and just starts from the beginning to end each time a swap is found. After the optimization, it is not possible for bubble sort to make more than ${n\choose 2}$ swaps, as you correctly state. – Shaull Feb 27 '13 at 11:13