Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 8 down vote accepted

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

share|cite|improve this answer
ok thanks that makes sense. – Fernando Martinez Feb 24 '13 at 18:42
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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