Time complexity of bubble sort

Worst case

This case arises when all the elements are arranged in descending order and we have to sort them in ascending order.

Pass                        Comparisons          Swaps

1                              n-1                n-1

2                              n-2                n-2

.                               .                 .

.                               .                 .

.                               .                 .

n-1                             1                 1

Now lets calculate the time complexity.

Number of comparisons = (n-1)  + (n-2) + ........... + 1 = n/2(n-1)  

Number of swaps = (n-1)  + (n-2) + ........... + 1 = n/2(n-1) 

Total no of swaps and comparisons = (n)(n-1)

We say f(n) = O(g(n)) , if c1*g(n)<=f(n)<=c2*g(n) for all n>=n0 

Constants c1 and c2 are positive real numbers
n0 = non negative integer    
f(n),g(n) = non negative functions of non negative arguments                                               

Take g(n) = n^2 and f(n) = (n)(n-1)

c1*n^2<=(n)(n-1)<=c2*n^2

We know 0<=(n)(n-1)<=n^2 ,so take c1=0,c2=1 and above condition is 
satisfied for all n>=1 (n0=1 here).

So , Time complexity = O(n^2) 

Time complexity = O(n^2)

Best Case

This case arises when all elements are sorted.So no swapping is required.But still the comparisons required are n/2(n-1).

Pass                        Comparisons          Swaps

1                              n-1                0

2                              n-2                0

.                               .                 .

.                               .                 .

.                               .                 .

n-1                             1                 0

Number of comparisons = (n-1)  + (n-2) + ........... + 1 = n/2(n-1)

So , Time complexity = O(n^2) 

Time complexity = O(n^2)

But if we terminate the algorithm when we notice no swaps are done in pass 1 then n-1 comparisons would be needed.So time complexity would be O(n).