Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

how to calculate Bubble sort Time Complexity

I was trying to understand the Data Structure and different algorithm, then i got confused to measure the Bubble sort time complexity.

for (c = 0; c < ( n - 1 ); c++) {
  for (d = 0; d < n - c - 1; d++) {
    if (array[d] > array[d+1]) /* For descending order use < */
    {
      swap       = array[d];
      array[d]   = array[d+1];
      array[d+1] = swap;
    }
  }
}

Now every Big O tells Best case O(n), Avg case(n2) and Worst Case(n2).But when i see the code, found in first phase inner loop run n time then in second phase n - 1, and n - 2 and so on. That means in every iteration its value goes down. For example if i have a[] = {4, 2, 9, 5, 3, 6, 11} so the total number of comparison will be -

1st Phase - 7 time
2nd phase - 6 time
3rd Phase - 5 time
4th Phase - 4 time
5th Phase - 3 time
6th Phase - 2 time
7th Phase - 1 time

so when i calculate the time it looks like = (7 + 6 + 5 + 4 + 3 + 2 + 1) + 7 = 35, but the worst time complexity is n2 as per doc.

so can Someone tell me how to calculate the correct value.

like image 256
Still Learning Avatar asked Apr 10 '15 07:04

Still Learning


4 Answers

Let's go through the cases for Big O for Bubble Sort

Case 1) O(n) (Best case) This time complexity can occur if the array is already sorted, and that means that no swap occurred and only 1 iteration of n elements

Case 2) O(n^2) (Worst case) The worst case is if the array is already sorted but in descending order. This means that in the first iteration it would have to look at n elements, then after that it would look n - 1 elements (since the biggest integer is at the end) and so on and so forth till 1 comparison occurs. Big-O = n + n - 1 + n - 2 ... + 1 = (n*(n + 1))/2 = O(n^2)

In your example, it may not examine these many elements in each phase as the array is not in descending order.

like image 169
gwhiz Avatar answered Oct 14 '22 05:10

gwhiz


So you've noticed that the total number of comparisons done is (n - 1) + ... + 2 + 1. This sum is equal to n * (n - 1) / 2 (see Triangular Numbers) which is equal to 0.5 n^2 - 0.5 n which is clearly O(n^2).

like image 25
Joren Avatar answered Oct 14 '22 03:10

Joren


it does comparison between two elements. so in 1st Phase - n-1 comparison. i.e, 6 2nd phase - n-2 comparison. i.e, 5 and so on till 1. and thus, sum = n(n-1)/2 i.e O(n^2).

if there is any error you can correct.....

like image 4
user5463721 Avatar answered Oct 14 '22 03:10

user5463721


O(n^2) = n(n-1)/2 is the right one.

As in the above example of 5 elements.

5(5-1)/2 == 10.

5(5+1)/2 != 10. 
like image 2
Shiraz Hussain Avatar answered Oct 14 '22 03:10

Shiraz Hussain