With the algorithm, derive the worst-case efficiency for Bubble Sort.
Answer:-
Bubble Sort is a brute-force sorting algorithm that repeatedly compares adjacent elements in a list and swaps them if they are out of order. After each pass, the largest unsorted element “bubbles up” to its correct position.
Algorithm (Pseudocode):
BUBBLESORT(A[0..n−1]):
for i ← 0 to n−2 do
for j ← 0 to n−2−i do
if A[j+1] < A[j]
swap A[j] and A[j+1]
Worst-Case Time Complexity Derivation:
In the worst case (when the input array is in strictly decreasing order), every pair of adjacent elements must be compared and swapped.
We analyze the total number of key comparisons first:
Number of Comparisons:
- Outer loop runs from i = 0 to n−2 → total n−1 iterations.
- Inner loop runs from j = 0 to n−2−i → decreasing by 1 each time.
So total comparisons:
Therefore,
Number of Swaps in Worst Case:
- When the array is reverse sorted, every comparison leads to a swap.
- So, the number of swaps is also the same as number of comparisons:
