Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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|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 at 0:01

2 Answers 2

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|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)$. –  Issam Laradji Feb 27 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|improve this answer
1  
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

 
discard

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.