for loop inside of a while loop - o(n) squared?

Question

I was comparing implementations of bubblesort and saw an alternative with a "for" loop inside of a "while" loop. Bubble sort is known to be o(n^2). is it still so if using a for loop inside of a while loop? I thought the time complexity of a while and an if statement are the same (ie linear):

Array.prototype.bubblesort = function() {
  var done = false;
  while (! done) {
    done = true;
    for (var i = 1; i < this.length; i++) {
      if (this[i - 1] > this[i]) {
        done = false;
        var tmp = this[i - 1];
        this[i - 1] = this[i];
        this[i] = tmp;
      }
    }
  }
  return this;
}

Using while instead of for does not affect asymptotic complexity. — Oriol
– Oriol, Commented Oct 18, 2015 at 22:31

user1196549 · Accepted Answer · 2015-10-18 23:16:17Z

The time complexity of a loop depends on the number of iterations that are performed, and the complexity of the individual loop bodies. The number of iterations depends on the loop exit condition, itself possibly depending on what's going on in the loop body.

You perform the analysis from the innermost loop towards the outermost ones.

In the case at hand, the inner loop (for) is always executed length times, and the body performs a bounded number of operations. Hence the complexity of the inner loop is O(length).

The discussion of the outer loop (while) is a little more complicated as it depends on the done flag, which is set by the inner loop. So the number of iterations of the outer loop is variable and depends on the content of the array. Without deeper study, we can say that there will be at least one iteration of the outer loop, and at most length iterations.

The latter statement can be justified as follows: the inner loop is such that it moves the largest element to the rightmost position, then the second largest to the before-rightmost position, and so on. Whatever the initial configuration, after length passes no more swaps can arise.

In conclusion, we can affirm that the algorithm takes time O(length²) in the worst case, and O(length) in the best case, i.e. when the array is initially sorted.

Collectives™ on Stack Overflow

for loop inside of a while loop - o(n) squared?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related