#### Complexity Analysis of Bubble Sorting

In Bubble Sort, n-1 comparisons will be done in 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So the total number of comparisons will be

(n-1)+(n-2)+(n-3)+.....+3+2+1

Sum = n(n-1)/2

i.e O(n2)

Hence the complexity of Bubble Sort isO(n2).

The main advantage of Bubble Sort is the simplicity of the algorithm.Space complexity for Bubble Sort is

**O(1)**, because only single additional memory space is required for**temp**variable**Best-case**Time Complexity will be

**O(n)**, it is when the list is already sorted.

## 0 comments:

## Post a Comment