So now that we understand how Bubblesort works, let's take a look at some pseudo-code.

bubblesort(array x){ boolean sorted <-- true do{ for i <-- 0 to x.length, incrementing i = i+1 if(x[i] > x[i+1]){ swap(x[i], x[i+1]) sorted <-- false } end FOR }while(NOT sorted) }

One thing I notice right off the bat is that on every swap, we also modify the value of a boolean. So if we make 1000 swaps, we take another 1000 steps to deal with our boolean. On top of that, our inner for loop takes linear time, and the outer loop takes approximately linear time as well. So n*n --> O(n^2).