The asymptotic order of the total number of comparisons in the standard bubble…

Concept

For an adjacent-comparison sorting process, each completed pass can place one extreme element in its final position, so the remaining unsorted portion becomes shorter by one.

When successive passes perform n-1, n-2, ..., 1 comparisons, the total is an arithmetic-series sum; its highest-degree term determines the asymptotic order.

Application

1. For n elements, the first pass compares n-1 adjacent pairs.

2. The later passes compare n-2, n-3, ..., 1 pairs because the sorted suffix grows by one element after each pass.

3. Therefore the total number of comparisons is (n-1)+(n-2)+...+1 = n(n-1)/2.

4. Expanding the expression gives (n2-n)/2; the n2 term dominates for large n, so the order is O(n2).

Cross-check

For n=5, the passes use 4+3+2+1=10 comparisons, and n(n-1)/2 gives 5×4/2=10. This agreement confirms the counting formula.

Thus the comparison count has order O(n2). The explicit offered growth classes are O(log n), O(n log n), and O(n); none equals O(n2), so the appropriate offered choice is “None of the listed classes.”