CODEWITHSUNDEEP
javascriptalgorithmsorting
devdropper87
devdropper87

Reputation: 4187

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

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;
}

Upvotes: 0

Views: 157

Answers (1)

user1196549
user1196549

Reputation:

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.

Upvotes: 1

Related Questions