Introduction

Bubble sort is a simple comparison-based sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items, and swapping them if they are in the wrong order. However, its simplicity comes with a trade-off: bubble sort is inefficient on large datasets, and its average and worst-case time complexity is O(n^2).

Understanding time complexity is crucial for analyzing how well bubble sort performs, particularly in terms of the number of comparisons and swaps it makes relative to the size of the input list. This article will explore how to calculate the time complexity of bubble sort through technical explanations and examples.

Algorithm Overview

Bubble sort repeatedly iterates through a list of items, compares each pair of adjacent items, and swaps them if they are out of order. Below is the typical implementation of bubble sort in Python:

1def bubble_sort(arr):
2    n = len(arr)
3    for i in range(n):
4        for j in range(0, n-i-1):
5            if arr[j] > arr[j+1]:
6                arr[j], arr[j+1] = arr[j+1], arr[j]
7
8# Example usage
9arr = [64, 34, 25, 12, 22, 11, 90]
10bubble_sort(arr)
11print("Sorted array:", arr)

Time Complexity Analysis

The time complexity of bubble sort concerns how the algorithm scales with increasing input sizes. We'll analyze it via the number of comparisons and swaps it performs.

Best Case

• Best Case Scenario: The list is already sorted.
• Number of Comparisons: The outer loop runs n times, and during the first pass (inner loop), n-1 comparisons are made. If no swaps are detected, the algorithm can terminate early. Thus, best-case complexity improves to O(n) if we optimize the algorithm to stop early if no swaps are made in a pass.

Average Case and Worst Case

• Average Case Scenario: The list is in random order.
• Worst Case Scenario: The list is sorted in reverse order.

In both cases, the analysis focuses on counting all possible pairs of elements:

1. Number of Comparisons: The inner loop runs (n - i - 1) times for each outer loop pass, where i ranges from 0 to n-1.
2. Total Comparisons:
   • First pass: n-1 comparisons
   • Second pass: n-2 comparisons
   • ...
   • Last pass: 1 comparison The sum of these comparisons is calculated using the arithmetic series formula: C = (n - 1) + (n - 2) + … + 1 = n(n - 1) / 2. Hence, the time complexity in both average and worst cases is O(n^2).
3. Number of Swaps: For a completely reverse-order list, this number approaches its maximum: the same series 1 + 2 + … + (n - 1) = n(n - 1) / 2. In average cases, swaps are about half of the comparisons due to random distribution.

Summary of Time Complexity

Space Complexity

While this article focuses on time complexity, it's worthwhile noting that bubble sort's space complexity is O(1) due to it being an in-place sorting algorithm, which requires only a constant amount of additional memory space for the swap operation.

Conclusion

Bubble sort is a simple yet inefficient sorting algorithm with a time complexity of O(n^2) in its average and worst cases, making it impractical for large datasets in most use cases. Nevertheless, its simplistic approach provides educational insights into sorting principles and algorithmic design. Understanding and calculating bubble sort's time complexity helps to appreciate its limitations and to recognize situations where more efficient algorithms should be applied.