Question

Write bubble sort algorithm and analysis it for best case and worst case time complexity using tabular method. Represent the time complexity using Theta(Ө) notation.

Answer 1

Bubble short algorithm-

start
arr[]
temp
 for(i=0;i<n-1;i++)
    for(j=0;j<n-i-1;j++)
      if(arr[j]>arr[j-1])
        temp=arr[j-1]
        arr[j-1]=arr[j]
        arr[j]=temp

Time complexity -

Best case analysis:

When array is already sorted but for loop will still check. So complexity is O(n)

Worst Case Analysis:

When array is not sorted, in that case two for loop will be initiated and run so complexity $O(n^2)$

Average case analysis:

It comprises O(n/2) passes, and O(n) comparison for each pass.

Hence, average case time complexity for the bubble sort $\theta (n^2)$

Space complexity -

It uses constant amount of space, hence the space complexity of the bubble sort is O(1).