how to calculate Bubble sort Time Complexity

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. 

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


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.