CODEWITHSUNDEEP
algorithmsortingcomplexity-theorybig-obubble-sort
ordinary
ordinary

Reputation: 6133

Why is bubble sort O(n^2)?

for (int front = 1; front < intArray.length; front++)
{
    for (int i = 0; i  < intArray.length - front; i++)
    {
        if (intArray[i] > intArray[i + 1])
        {
            int temp = intArray[i];
            intArray[i] = intArray[i + 1];
            intArray[i + 1] = temp;
        }
    }
}

The inner loop is iterating: n + (n-1) + (n-2) + (n-3) + ... + 1 times.

The outer loop is iterating: n times.

So you get n * (the sum of the numbers 1 to n)

Isn't that n * ( n*(n+1)/2 ) = n * ( (n^2) + n/2 )

Which would be (n^3) + (n^2)/2 = O(n^3) ?

I am positive I am doing this wrong. Why isn't O(n^3)?

Upvotes: 20

Views: 50833

Answers (6)

Giang Nguyen
Giang Nguyen

Reputation: 498

This is another version to speed up bubble sort, when we use just a variable swapped to terminate the first for loop early. You can gain better time complexity.

#include <stdio.h>
#include <stdbool.h>
#define MAX 10

int list[MAX] = {1,8,4,6,0,3,5,2,7,9};

void display(){
   int i;
   printf("[");

   for(i = 0; i < MAX; i++){
      printf("%d ",list[i]);
   }

   printf("]\n");
}

void bubbleSort() {
   int temp;
   int i,j;

   bool swapped = false;       

   // 1st loop
   for(i = 0; i < MAX-1; i++) { 
      swapped = false;

      // 2nd loop
      for(j = 0; j < MAX-1-i; j++) {
         printf("     Compare: [ %d, %d ] ", list[j],list[j+1]);

         if(list[j] > list[j+1]) {
            temp = list[j];
            list[j] = list[j+1];
            list[j+1] = temp;

            swapped = true;
         }

      }

      if(!swapped) {
         break;
      }

      printf("Loop number %d#: ",(i+1)); 
      display();                     
   }

}

main(){
   printf("Before: ");
   display();
   printf("\n");

   bubbleSort();
   printf("\nAfter: ");
   display();
}

Upvotes: 0

winuxguy
winuxguy

Reputation: 31

k=1(sigma k)n = n(n+1)/2
because:
  s = 1 +  2    + ... + (n-1) + n
  s = n + (n-1) + ... + 2     + 1
+)
===================================
  2s = n*(n+1)
   s = n(n+1)/2
in bubble sort, 
(n-1) + (n-2) + ... + 1 + 0 times compares 
which means, k=0(sigma k)n-1
, k=0(sigma k)n-1 equals [k=1(sigma k)n] - n
therefore, n(n+1)/2 - n = n(n-1)/2
which is 1/2(n^2-n) => O(1/2(n^2-n))
in big O notation, we remove constant, so
O(n^2-n)
n^2 is larger than n
O(n^2)

Upvotes: 3

Travis Pessetto
Travis Pessetto

Reputation: 3298

How you basically calculate N...

  • Each line: +1

  • Each Loop *N

    So you start adding numbers get to your first loop now you have N+1, you keep going and you eventually get N*N or N^2 for the time plus some number. Pulling off the number as it is generally insignificant compared to N.

Pretty much N is a representation of all the items in the loop kind of like 1,2,3...N. So it is simply representing a number not how many times a loop, loops.

Upvotes: 2

GL770
GL770

Reputation: 3210

Your inner loop is iterating, IN TOTAL, as you said n + (n-1) + (n-2) + (n-3) + ... + 1 times. So it is O(n + (n-1) + (n-2) + (n-3) + ... + 1) = O(n(n+1)/2) = O(n^2)

Upvotes: 11

NominSim
NominSim

Reputation: 8511

The inner loop iterates n times(in worst case): 

for(int i = front; i < intArray.length; i++)

The outer loop iterates n times:

for(int front = 0; front < intArray.length; front++)

Therefore O(n^2)

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372814

You are correct that the outer loop iterates n times and the inner loop iterates n times as well, but you are double-counting the work. If you count up the total work done by summing the work done across each iteration of the top-level loop you get that the first iteration does n work, the second n - 1, the third n - 2, etc., since the ith iteration of the top-level loop has the inner loop doing n - i work.

Alternatively, you could count up the work done by multiplying the amount of work done by the inner loop times the total number of times that loop runs. The inner loop does O(n) work on each iteration, and the outer loop runs for O(n) iterations, so the total work is O(n2).

You're making an error by trying to combine these two strategies. It's true that the outer loop does n work the first time, then n - 1, then n - 2, etc. However, you don't multiply this work by n to to get the total. That would count each iteration n times. Instead, you can just sum them together.

Hope this helps!

Upvotes: 22

Related Questions