HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMinor

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

Submitted by: @import:stackexchange-cs··
0
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.

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

Context

StackExchange Computer Science Q#10058, answer score: 8

Revisions (0)

No revisions yet.