Count amount of times loop runs (Big O)

Question

I'm given a pseodocode statement as such:

function testFunc(B)
  for j=1 to B.length-1
     for i=1 to B.length-j
       if(B[i-1] > B[i]
         swap B[i-1] and B[i]

And I'm told to show that this algorithm runs in Big o O(n^2) time.

So I know that the first for loop runs n times, because I believe it's inclusive. I'm not sure about the rest of the lines though, would the second for loop run n-2 times? Any help would be much appreciated.

Answer 1

The inner loop runs a decreasing number of times. Look at a concrete example. If B.length were 10, then the contents of the inner loop would be executed 10 times, then 9 times, and so on, down to 1 time.

Using Gauss' equation of:

n(n + 1) / 2

you can see that the inner code would be executed 55 times in that example. (10(10 + 1)/2 = 55)

So, it follows that for n times, it would run n(n + 1) / 2 times. This is equivalent to:

1/2 n^2 + 1/2 n

In terms of Big-Oh, the co-efficients and the smaller values of n are ignored, so this is equivalent to O(n^2).