The worst-case complexity of the bubble sort algorithm is O(n²)
. This occurs when the input data is in reverse order, requiring the algorithm to perform the maximum number of comparisons and swaps to sort the array
. Here's why:
- Bubble sort involves nested loops
. The outer loop runs O(n) times, and the inner loop performs O(n) comparisons in each pass
- In the worst-case scenario, the algorithm needs to go through the array the maximum number of times, comparing and swapping every pair of adjacent elements in each pass
. This leads to a total of n(n-1)/2 comparisons and swaps
- Therefore, the worst-case time complexity is O(n * n) = O(n²)
