2

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.

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.