Running time of the specified Bubble Sort Algorithm

Question

I have been working on a few algorithm questions the last few days, and one bubble sort problem in particular has been giving me headaches.

for (k=1; k <= A.length - 1; k++) { //Line 1
 for (m=1; m <= A.length - k; m++) { //Line 2
 if (A[m-1] > A[m]) { //Line 3
 Swap (A[m-1], A[m]); //Line 4
}

Now, I am supposed to find the running time of this algorithm in the worst case scenario, and I know that it is O(n^2), but the problem I am having is finding out how many times is each line executed.

For example, line 1 is going to take n units of time, while line 4 depends on the complexity of function Swap. However, line 2 on the other hand is going to take [(n-1) * ?] units of time (I tried finding out exactly and I got (n-1)*n) and I am stomped with finding how to do the IF statement, but I assume it will take (? - 1) times. IF anyone could give me an explanation on how to do this, I would greatly appreciate it.

• Evan Plaice: As a new user, keep in mind that posting homework questions is strongly discouraged here. With that said, it looks as though you framed the question in a way that seeks an approach to finding the solution yourself, rather than asking for the solution. So, there's no issue.

Answer 1

Don't worry about the if statement. If your data is random, you can assume that the if statement will be true about half the time, but you don't need to care about that. The basic rule of thumb for this type of analysis is very simple: count loops. When it comes down to it, what's going to determine how long your algorithm runs is how many times the if statement in its entirety runs.

That's why big-O is expressed as an asymptote. You have 2 nested loops, and as the size of the data set increases, the total runtime is weighted more and more heavily on the square of the size, therefore the time complexity is on the order of n^2. To visualize this, remember that statistically, you expect the if statement to be true half the time. Try graphing 0.5(x^2), and then graph (x^2), and see how the 1/2 scaling becomes less and less important as x grows larger and larger.