What is the worst case and average case complexity of bubblesort?

Answer 1

Best case: O(n)

Worst case: O(n2)

Let's assume we're sorting data in an array of length n. Let's also assume that we're sorting in ascending order (low-high).

The worst case is that you will have the smallest value in the last space in the array. This means that it will move exactly once each pass towards the first space in the array. It will take n-1 passes to do this, doing n comparisons on each pass: O(n2)

The best case is that the data comes to us already sorted. Assuming that you have a smart implementation (which you should, because it's easy) which stops itself once a pass makes no changes, then we only need to do n comparisons over a single pass: O(n)

Answer 2

Short answerBest case: O(n)

average and worst case: O(n2)

Long answerLet's assume we're sorting data in an array of length n. Let's also assume that we're sorting in ascending order (low-high).

The worst case is that you will have the smallest value in the last space in the array. This means that it will move exactly once each pass towards the first space in the array. It will take n-1 passes to do this, doing n comparisons on each pass: O(n2)

The best case is that the data comes to us already sorted. Assuming that you have a smart implementation (which you should, because it's easy) which stops itself once a pass makes no changes, then we only need to do n comparisons over a single pass: O(n)

Average is trickier... but it is O(n2)

Read more: What_is_the_worst_case_and_best_case_time_complexity_of_bubblesort

Answer 3

Consider sorting an array of elements in ascending order using bubble sort. Bubble sort bubbles the greatest element to the last position in its first iteration, the second largest element to the second last position in its second iteration and so on. Due to this technique, the following cases occur:

1) Best case: This occurs when the array is already sorted in ascending order. In such situation, the bubble sort algorithm simply scans through the array rendering a complexity of O(n).

2) Average case: This occurs when the elements are arranged in random order. It has a time complexity of O(n2).

3) Worst case: This occurs when the array is reverse sorted ie sorted in descending order. In this case, the elements the elements are swapped in every iteration rendering a complexity of O(n2).

Answer 4

Best case is O(n) when the array is already sorted. Worst case is O(n*n). The average case is also O(n*n). Due to its poor performance, bubble sort cannot handle large data sets efficiently and has no practical uses beyond academic study; it is often cited as an example of how not to write a sorting algorithm.

Answer 5

Worst case performanceО(n2)Best case performanceО(n2)Average case performanceО(n2)Worst case space complexityО(n) total, O(1) auxiliary