What is the worst-case time complexity of bubble sort for an input of size x?

Concept

Bubble sort maintains this invariant: after each pass, the largest element still in the unsorted prefix is placed at the end of that prefix, so the sorted suffix grows by one position.

In the conventional in-place algorithm, each adjacent comparison and swap takes constant time. Therefore, total running time is proportional to the comparisons and swaps made across the shrinking passes.

Application

1. For a reverse-ordered array of size x, the first pass examines x−1 adjacent pairs and moves the largest value to its final position; many of those comparisons also require swaps.

2. One position is then fixed, so the unsorted prefix is shorter. The next pass makes x−2 comparisons, and the later passes continue with x−3, ..., 1 comparison. A reverse-ordered input requires every shrinking pass rather than permitting early termination.

3. Hence the total number of comparisons is (x−1)+(x−2)+⋯+1 = x(x−1)/2.

4. The leading term of x(x−1)/2 is x2/2. Big-O notation ignores constant factors and lower-order terms, so the growth is O(x2).

Cross-check

For x=4, the pass counts are 3, 2, and 1, giving 6 comparisons; the formula 4(4−1)/2 also gives 6. The invariant predicts a sorted suffix of lengths 1, 2, and 3 after those passes.

Contrast

• Linear growth would describe work comparable to a fixed number of full-array scans.

• Logarithmic growth would describe a process that reduces the remaining problem by a constant factor at each stage.

• Linearithmic growth would combine linear work with logarithmically many stages.

• Bubble sort instead accumulates a decreasing arithmetic series of comparison counts, whose leading term is quadratic.

Result: The worst-case time complexity of bubble sort is O(x2).