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.
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.
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).
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.....
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With