What is the time complexity of bubble sort?

In the worst and average cases, $O(n^2)$, where $n$ is the number of elements in the list. In the best case (when the list is already sorted) — $O(n)$.

# Bubble sort function
def bubble_sort(arr):
    n = len(arr)
    # Traverse through all array elements
    for i in range(n):
        # Flag for optimization: if no swaps occurred during a pass, the array is sorted
        swapped = False
        # Last i elements are already in place
        for j in range(0, n-i-1):
            # Swap if the element found is greater than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
        # If no two elements were swapped by inner loop, then break
        if not swapped:
            break
    return arr

# Usage examples
# Worst case (reverse sorted list)
arr_worst = [5, 4, 3, 2, 1]
bubble_sort(arr_worst) # Performs n*(n-1)/2 comparisons and swaps

# Average case (random list)
arr_average = [3, 1, 4, 1, 5, 9, 2, 6]
bubble_sort(arr_average) # In average, the number of comparisons and swaps is also proportional to n^2

# Best case (sorted list)
arr_best = [1, 2, 3, 4, 5]
bubble_sort(arr_best) # Thanks to optimization, only one pass through the list is performed, n comparisons

Scenario	Time Complexity
Worst case	$O(n^2)$
Average case	$O(n^2)$
Best case	$O(n)$