Question

Given the recursive bubble sort algorithm, analyze its time complexity in terms of Big O.

bubbleSort(A[], n)
{
// Base case
if (n == 1)
return;
  
// One pass of bubble sort. After
// this pass, the largest element
// is moved (or bubbled) to end.
for (i=0; i<n-1; i++)
if (A[i] > A[i+1])
swap(A[i], A[i+1]);
  
// Largest element is fixed,
// recur for remaining array
bubbleSort(A, n-1);
}

Answer 1

The true analysis of algorithm depends on the actual array because of the condition A[i] > A[i+1]

However, to determine the complexity in terms of Big O notation i.e. upper bound, we consider the worst case which is the array sorted in descending order.

(n-1 is added because of iterations from 0 to n-2)

With base case as and

Observing the pattern we find that,