What's the Time and Space Complexity of Bubble Sort vs Selection Sort?

Bubble sort and selection sort both have average and worst-case time complexity of $O(n^2)$ and auxiliary space complexity of $O(1)$. However, an optimized bubble sort has a best-case time complexity of $O(n)$, while selection sort remains $O(n^2)$ even when the data is already sorted.

Here, $n$ represents the number of elements in the array.

Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. Across its passes, the number of comparisons is approximately

$$(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2},$$

which grows proportionally to $n^2$. An optimized version uses a Boolean flag to stop after one pass with no swaps, producing $O(n)$ time for already sorted data.

Selection sort repeatedly searches the unsorted section for its minimum element and places it in the next sorted position. It still performs approximately $\frac{n(n-1)}{2}$ comparisons regardless of the original order, so its best, average, and worst cases are all $O(n^2)$.

Although their asymptotic time is the same, their operation counts differ. Selection sort performs at most $n-1$ swaps, whereas bubble sort can perform $\frac{n(n-1)}{2}$ swaps in reverse order. This matters when writes are expensive, but it does not change either algorithm's $$ classification. Big O ignores constant factors and lower-order terms in growth.

Both are in-place algorithms because they use only a fixed number of extra variables. Therefore, their auxiliary space does not increase with $n$, giving $O(1)$.

A common misconception is that selection sort becomes faster in Big O terms when the array is sorted. It may perform fewer swaps than bubble sort, but it still checks every remaining element when selecting each minimum.

For IB Computer Science B2.4, state the case being analysed, define $n$, and justify the complexity using passes or comparisons. Do not give only the Big O value when the command term is explain.