10

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.

keepmoving
  • 1,813
  • 8
  • 34
  • 74
  • `O(n^2)` very much does *not* mean that the total number of steps will exactly equal `n^2`. – AakashM Apr 10 '15 at 08:06
  • 3
    To add to @AakashM, you first need to understand the meaning of `O(...)` notation. See for example: http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o/ – Abhay Apr 10 '15 at 12:44

7 Answers7

23

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.

gwhiz
  • 613
  • 1
  • 4
  • 9
  • 2
    As a definition Big Oh (O) notation denotes worst case scenario only, while Big Omega Ω(O) notation denotes best case scenario! – Tejas C Mar 03 '17 at 20:01
  • The O(n) variant of BubbleSort is the one that stops iterating when there's nothing else to sort. The code in this question always runs the inner loop approx. n^2/2 times, even thought it doesn't always swap. So this code is O(n^2) for all inputs. – giusti Dec 29 '17 at 22:01
  • Also, Big-O is not tied to best/worst case. Big-O means "upper-bound". Omega means "lower-bound". It makes sense to say that BubbleSort is Ω(n) and O(n^2) for all inputs, but it also makes sense to say that it's O(n) in the best case and even that it's Ω(n^2) in the worst case. – giusti Dec 29 '17 at 22:05
7

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).

Community
  • 1
  • 1
Joren
  • 14,472
  • 3
  • 50
  • 54
4

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.....

user5463721
  • 41
  • 1
2

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.
slfan
  • 8,950
  • 115
  • 65
  • 78
Shiraz Hussain
  • 21
  • 3
2

Best case: This time complexity can occur if the array is already sorted. That means no swapping occurs and only 1 iteration of n elements will be there.

So time complexity is O(n).

Worst case: This time complexity can occur if the array is already sorted but is descending order.

In 1st iteration, number of comparison = n-1
In 2nd iteration, number of comparison = n-2
.......................................................................
.......................................................................
.......................................................................
In (n-2)th iteration, number of comparison = 2
In (n-1)th iteration, number of comparison = 1

for n elements total number of iteration= n-1
Total number of comparison S = (n-1)+ (n-2) +........ +    2    +    1
We can write this also          S =      1 +      2 + ........+(n-2) + (n-1)
................................................................................................................................                                           2S =       n +     n + ......... +     n +       n .... [Adding both line]
                                          2S = n(n-1) ..... [as total no of iteration = n-1]
                                           S = n(n-1)/2
In polynomial function, highest order of n is considered as time complexity.
So, Time Complexity is O(n^2)

Chaitaly
  • 21
  • 4
1

Explaining for worst case here : 

elements = raw_input("enter comma separated elements : ")
elements = elements.split(',')
elements = map(int, elements)
length = len(elements)

for i in xrange(length - 1):
    print "outer pass : ", i
   for j in xrange(length - i - 1):
       print "inner pass : ", j
       if elements[j] > elements[j + 1]:
           elements[j + 1], elements[j] = elements[j], elements[j + 1]
       print "elements : ", elements
print elements

Output :

enter comma separated elements : 5,4,3,2,1

outer pass : 0

inner pass : 0

elements : [4, 5, 3, 2, 1]

inner pass : 1

elements : [4, 3, 5, 2, 1]

inner pass : 2

elements : [4, 3, 2, 5, 1]

inner pass : 3

elements : [4, 3, 2, 1, 5]

outer pass : 1

inner pass : 0

elements : [3, 4, 2, 1, 5]

inner pass : 1

elements : [3, 2, 4, 1, 5]

inner pass : 2

elements : [3, 2, 1, 4, 5]

outer pass : 2

inner pass : 0

elements : [2, 3, 1, 4, 5]

inner pass : 1

elements : [2, 1, 3, 4, 5]

outer pass : 3

inner pass : 0

elements : [1, 2, 3, 4, 5]

[1, 2, 3, 4, 5]

Thus first iteration all n elements are scanned, it would scan n - 1 elements in the next iteration. So on for all the elements.

n + n - 1 + n - 2 ... + 1 = (n * (n + 1))/2 = O(n^2)

Vishvajit Pathak
  • 3,351
  • 1
  • 21
  • 16
0

For n number of numbers, total number of comparisons done will be (n - 1) + ... + 2 + 1. This sum is equal to (n-1) * n / 2 (see Triangular Numbers) which equals to 0.5 n^2 - 0.5 n i.e. O(n^2)

SHYAM KUMAR SINHA
  • 1