Bubble Sort Best Case Analysis

Given Input: [1 3 6 7 8 ]

 

Best Case Analysis

****************

1. The best case for bubble sort occurs when the list is already sorted or nearly sorted.


2. In the case where the list is already sorted, bubble sort will terminate after the first iteration, since no swaps were made.


3. Any time that a pass is made through the list and no swaps were made, it is certain that the list is sorted


4. The term best case performance is used to describe an algorithm's behavior under optimal conditions (i.e) for sorting, given inputs are sorted list.

 

For sorted list , bubble sort requires minimum no. of comparisons , it leads to better performance.

 

Total No of elements : 5

 

Total No of passes : 5-1 = 4 passes

 

For all the passes , bubble sort takes 10 comparisons in best case analysis.

 

Time complexity for Best Case : O(n²)

 

Back...