What will be the maximum number of comparisons performed by bubble sort to sort n elements?

Bubble sort performs comparisons by repeatedly traversing the array and swapping adjacent elements if they are out of order. In the worst case (reverse-sorted array), the outer loop runs n times and the inner loop runs up to n-1, n-2, ... 1 times, yielding (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons, which simplifies to O(n²). Options A and B underestimate the complexity, while option D is not a standard Big O notation.

Step-by-step Derivation:
Bubble sort algorithm:

• Outer loop: i from 0 to n-1 (n iterations)
• Inner loop: j from 0 to n-i-1 (variable iterations)

Total comparisons in worst case:

• Pass 1: n-1 comparisons
• Pass 2: n-2 comparisons
• Pass 3: n-3 comparisons
• ...
• Pass n: 0 comparisons

Sum = (n-1) + (n-2) + (n-3) + ... + 1 + 0 = n(n-1)/2

For large n: n(n-1)/2 ≈ n²/2, which is O(n²)

This is the worst-case time complexity when the array is sorted in reverse order.