17. Analyzing Bubble Sort Efficiency

As we saw, Bubble Sort uses nested loops, which typically indicates quadratic time complexity.

Time Complexity Analysis

• Worst Case: O(N²)
  • Occurs when the array is sorted in reverse order. The inner loop must perform maximum comparisons in every pass.
• Best Case: O(N)
  • Occurs if the array is already sorted. If we add a flag to detect if any swaps occurred in a pass, we can stop early after the first O(N) pass, achieving linear time.
• Average Case: O(N²)

Space Complexity

• Space Complexity: O(1) auxiliary space.
  • Bubble sort is an in-place sorting algorithm, meaning it only requires a minimal, constant amount of extra memory (usually just for temporary variables used in the swap).