Course contentsShow
← Computer Science
Lesson 742 of 2,87218. Sorting AlgorithmsFree lesson

Bubble Sort: Analysis

Analyzing bubble sort's O(n²) time complexity in worst and average cases, O(n) best case with optimization.

Bubble Sort: Analysis

You'll learn: how to reason about bubble sort's performance across different input conditions and understand why it's O(n²) in most cases.

Now that you've seen how bubble sort works—repeatedly swapping adjacent elements that are out of order—it's time to analyze when it performs well and when it struggles.

Worst-Case Time Complexity: O(n²)

Imagine sorting a completely reversed array, like [5, 4, 3, 2, 1]. The largest element (5) must "bubble" all the way to the end in pass 1. Then 4 must bubble to the second-to-last position in pass 2, and so on.

  • Pass 1: (n - 1) comparisons
  • Pass 2: (n - 2) comparisons
  • Pass 3: (n - 3) comparisons
  • ...continuing until Pass n-1: 1 comparison

Total comparisons = (n-1) + (n-2) + ... + 1 = n(n-1)/2, which simplifies to O(n²).

Average-Case: Also O(n²)

Even with random data, on average about half the pairs will be out of order. You still perform roughly the same quadratic number of comparisons, making the average case O(n²) as well.

Best-Case with Optimization: O(n)

Here's where bubble sort can shine: if the array is already sorted, an optimized version that tracks whether any swaps occurred can exit after just one pass through the array. That's only (n-1) comparisons—O(n) time.

Think of it like checking if a bookshelf is already alphabetized: you scan once, find everything in order, and you're done.

Space Complexity: O(1)

Bubble sort only needs a temporary variable for swapping, making it an in-place algorithm.

Key Takeaway: Bubble sort has O(n²) worst and average-case time complexity due to nested comparisons, but with an optimization flag checking for swaps, achieves O(n) best-case performance on already-sorted data.