Bubble sort recurrence formula

1.7k Views Asked by Bumbble Comm At 27 Mar 2026 - 9:43

I wrote the following recursive version of Bubble sort Algorithm:

fun Bubb(A,i,j):
if (j = 1) then
    {return A[j]}
if (A[i] > A[i+1]) then
    {swap A[i] and A[i+1]}
Bubb(A,i+1,j)
Bubb(A,i,j+1)

Although I know Bubble sort takes O(n^2) time in the worst case. I am not sure if my the following recurrence formula is really correct:

T(n) = T(n)T(n-1) + O(1)

Since we compare two elements at each time, we say T(n)T(n-1) plus a constant time taken for swap operation.

Can someone verify if my understanding is correct?

Thank you very much.