What is the time complexity of bubble sort in the worst case?

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the list is sorted. In the worst-case scenario, which occurs when the array is sorted in reverse order, the algorithm must make comparisons and perform swaps for each element in the list.

Specifically, for an array of size n, the first pass through the array will require n-1 comparisons, the second pass will require n-2 comparisons, and so on, until the last pass requires just 1 comparison. Thus, the number of comparisons is:

(n-1) + (n-2) + (n-3) + ... + 1 = n(n-1)/2,

which simplifies to O(n^2) in big-O notation. This quadratic time complexity arises because for each element, the algorithm potentially traverses the entire array, leading to a significant increase in execution time as the number of elements increases.

In this context, the answer accurately reflects the behavior of bubble sort under the worst-case scenario, where the number of swaps and comparisons scales quadratically with the size of the input array.