0

I wrote this bubble sort function but I am having a hard time figuring out the time complexity of it.

function bubbleSort(items) {  
    for (var i = items.length; i > 0; i--) {
      for (var j = 0; j < i; j++) {
        if (items[j] > items[j + 1]) {
          var temp = items[j];
          items[j] = items[j + 1];
          items[j + 1] = temp;
        }
      }
    }

    return items;
}

I know that the outer loop has time complexity of O(n). But what is the time complexity of the inner loop (since it goes through one less element of items on each pass) ?

georgej
  • 3,041
  • 6
  • 24
  • 46
  • google for "bubble sort complexity", to find references such as [this one in Wikipedia](https://en.wikipedia.org/wiki/Bubble_sort#Performance). Or search on SO, which turns up 375 results. –  Jan 22 '17 at 05:18

3 Answers3

1

The inner loop is O(n). At the beginning it will execute n times, at the end 1 time. On average it will execute n/2 times. Constant factors don't matter, so that's O(n).

Together, the overall runtime is therefore O(n2).

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
1

If you consider how many times inner loop is run, you may have a better idea:

1st run : N times, 
2nd run: N-1 times 
... 
Nth run: 1 time.

If you add them all 

N + (N-1) + (N-2) + ... + 1 = [N * (N+1)]/2

times. That makes O(N^2). For more information, check this answer here: https://stackoverflow.com/a/29556003

Community
  • 1
  • 1
Görkem Özer
  • 504
  • 5
  • 13
  • 1
    I don't understand. If that question/answer provides "more information", does not that make this question a duplicate? –  Jan 22 '17 at 05:23
  • @torazaburo You are right, since I couldn't find "mark as duplicate" option from mobile app, I put URL of the answer below. Thanks for the reminder btw. – Görkem Özer Jan 22 '17 at 15:03
1

One way to calculate the time complexity of your algorithm is to note that the inner loop executes i iterations where i ranges from n down to 1 (where n is the length of the input). This means that we can do a summation to get the total number of steps in the algorithm:

n + (n-1) + ... + 3 + 2 + 1

This summation has a familiar closed formula:

n*(n+1) / 2

This formula is clearly O(n^2).

Code-Apprentice
  • 81,660
  • 23
  • 145
  • 268