gotchaMinor
Why does bubble sort do $\Theta(n^2)$ comparisons on an $n$ element list?
Viewed 0 times
thetawhybubbleelementdoessortlistcomparisons
Problem
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.
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.
Solution
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)$.
Observe that even under some optimizations of the naive bubble sort, the runtime is still ${n\choose 2}=\theta(n^2)$.
Context
StackExchange Computer Science Q#10058, answer score: 8
Revisions (0)
No revisions yet.