Recursive Bubble Sort Complexity

Question

I have this code for a recursive bubble sort:

def bubble_sort_recursive(list_):
    global counter
    for i in range(len(list_)):
        counter += 1
        try:
            if list_[i + 1] < list_[i]:
                list_[i], list_[i + 1] = list_[i + 1], list_[i]
                bubble_sort_recursive(list_)
        except IndexError:
            continue
    return list_

The counter is initialized with zero outside the function, so I can count the number of times the elements were iterated.

I was told that the complexity of bubble sort is O(N^2). But when I run with a reversed list (worst case) with size 3, the counter finishes with the value 12, shouldn't it be 9?

The same happens for other sizes: 4 -> 28 5 -> 55

What is happening?

Answer 1

The meaning of $O(n^2)$

I was told that the complexity of bubble sort is $O(n^2)$. But when I run with a reversed list (worst case) with size 3, the counter finishes with the value 12, shouldn't it be 9?

Had $O(n^2)$ meant $n^2$, we should have written it as $n^2$ instead of that funny looking $O(n^2)$. Instead, $O(n^2)$ means no more than $n^2$ roughly. By "roughly", we mean we do not care about a constant multiplier, be it 0.01 or 2019 or a million. That is, $O(n^2)$ represents a function of $n$ that is $0.01n$ or less. Or a function that is $2019n$ or less. Or a function that is $1000000000n$ or less.

Because of that constant multiplier, even if that counter for a list of size 3 ends up with 9999, it does not contradict the bound $O(n^2)$, although it could be considered a warning sign that the right bound might be bigger such as $O(n^3)$ instead.

The counter and the time-complexity

What is the meaning of the counter in the algorithm? It counts how many times the algorithm has entered into the loop body.

For each call of the algorithm, if we exclude the subcall of the algorithm cause by an inversion, list_[i + 1] < list_[i], the counter will be increased len(list_) times, namely, $n$ times.

Assume the input list was reversely sorted, the worst case for time-complexity. There are $n(n-1)/2$ inversions, which lead to calling the algorithm $n(n-1)/2$ times. There is also the initial call of the algorithm. In total, the algorithm is called $1+n(n-1)/2$ times. So, in the end, the value of the counter is $n\cdot(1+n(n-1)/2)$. For example, if $n=3$, counter ends up with $3(1+3(3-1)/2)=12$, as mentioned in the question.

Note that $n\cdot(1+n(n-1)/2)=\Theta(n^3)$. Since the time-complexity of the algorithm is about a constant multiple of that counter, we conclude that the time-complexity of the algorithm is $O(n^3)$.

An improved version of the algorithm

Here are a few places where the algorithm can be improved.

1. Instead of for i in range(len(list_)), it could have been for i in range(len(list_)-1). The try ... except can be spared.

2. The return value of bubble_sort_recursive is never used.

3. When we have swapped two elements, list_[i + 1] and list_[i] as they found to be the first unsorted pair of elements, the first $i$ elements remain sorted. So, we can avoid checking the adjacent pairs in those $i$ elements then.

4. Consider the $n-1$ comparisons made in one call of the algorithm but not in the possible recursive call inside that call. When an inversion is found by one of the comparisons, a recursive call, which will try to find an inversion from scratch, will be made. That means all later comparisons will not succeed and, hence, will not change the list in any way. So, we can break the loop after the recursive call.

Here is the improved version.

def bubble_sort_recursive_improved(list_, begin):
    global counter
    for i in range(begin, len(list_) - 1):
        counter += 1
        if list_[i + 1] < list_[i]:
            list_[i], list_[i + 1] = list_[i + 1], list_[i]
            bubble_sort_recursive_improved(list_, 0 if i == 0 else i - 1)
            break

# import sys
# sys.setrecursionlimit(max(1000, n * n // 2))
numbers = [5, 4, 3, 2, 1]
counter = 0
bubble_sort_recursive_improved(numbers, 0)
print(numbers, counter)

---

Exercise 1. Explain how the improved algorithm works correctly.

Exercise 2. Show that the improved algorithm runs in $O(n^2)$ time. In particular, counter is at most $n(n-1)$.