PHP 7 Data Structures and Algorithms

Complexity of bubble sort

For the first pass, in the worst case, we have to do n-1 comparison and swapping. For the n-1th pass, in the worst case, we have to do only one comparison and swapping. So, if we write it step by step then we will see:

Complexity = n - 1 + n - 2 + .......... + 2 + 1 = n * ( n - 1)/2 = O(n²)

Thus, the complexity of bubble sort is O(n²). However, there is some constant time required to assign a temporary variable, swapping, go through inner loops, and so on. We can ignore them since they are constant.

Here is the time complexity table for bubble sort, for best, average, and worst case scenarios:

Best time complexity	Ω(n)
Worst time complexity	O(n2)
Average time complexity	Θ(n2)
Space complexity ...