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

-

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)$.
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 at 11:13