Bubble Sort Analysis

for i = n down to 2
    for j = 1 to i-1
	if A[j] < A[j+1]
	    swap(A,i,j)

During the explorations, we learned that the number of comparisons bubble sort makes is not affected by the values in the data, so the analysis for worst-case, best-case and average case are all the same and depend only on the for loops in the pseudocode.

Clearly, the outer loop runs n times. The only complexity in this analysis in the inner loop. If we think about a single time the inner loop runs, we can get a simple bound by noting that it can never loop more than n times. Since the outer loop will make the inner loop complete n times, the comparison can't happen more than O(n²) times.

However, that seems to be a very high bound because the last time the inner loop runs, it will only make one comparison (which is a lot less than the n we were counting above). The first time the inner loop runs, it will make n-1 comparisons, the next time it will make n-2 comparisons; and so on. Therefore, the actual number of comparisons is

which has a value of (n-1)n/2 which is also O(n²). It is interesting that, in this case, our rough estimate which seems heavy handed turns out to be correct. One of the skills in analysis is know when you have gone deep enough in your analysis. This time we could have stopped with the rough guess and experience would tell us it was accurate.

The bottom line is that Bubble Sort has worst, best and average case run-time of O(n²).