10

I was trying to understand the data structure and different algorithm, but 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 the 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 times and then in the 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 documentation.

How can I calculate the correct value?

2
  • O(n^2) very much does not mean that the total number of steps will exactly equal n^2.
    – AakashM
    Apr 10, 2015 at 8:06
  • 3
    To add to @AakashM, you first need to understand the meaning of O(...) notation. See for example: stackoverflow.com/questions/487258/…
    – Abhay
    Apr 10, 2015 at 12:44

7 Answers 7

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.

3
  • 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 3, 2017 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, 2017 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, 2017 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).

4

It does comparison between two elements. So in the first phase - n-1 comparison. I.e., 6

Second phase - n-2 comparisons. I.e, 5 and so on till 1.

And thus, sum = n(n-1)/2 i.e., O(n^2).

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

1

Explaining for the worst-case scenario 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, in the first iteration, all n elements are scanned. It would scan n - 1 elements in the next iteration. And so on for all the elements.

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

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)

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.