A Performance Analysis of Bubble Sort

It is easier to see that bubble sort involves two levels of loops:

• An outer loop: This is also called passes. For example, pass one is the first iteration of the outer loop.
• An inner loop: This is when the remaining unsorted elements in the list are sorted, until the highest value is bubbled to the right. The first pass will have N-1 comparisons, the second pass will have N-2 comparisons, and each subsequent pass will reduce the number of comparisons by one.

Due to two levels of looping, the worst-case runtime complexity would be O(n²).