Prashnikaप्रश्निका
Code
About
‹ Back to the paper

Question 2(d)

2 marks

Computer ScienceISC 2020 Computer Science Paper 1Short answerComplexity and Big O notation

Answer the following in short.

State the best case and the worst case complexity for bubble sort algorithm.

Answer

Answer

Bubble sort: Best case: $O(n)$. This happens when the array is already sorted; the optimised bubble sort makes one pass, finds no swaps and stops. Worst case: $O(n^2)$. This happens when the array is in reverse order; every pass makes swaps and about $n(n-1)/2$ comparisons are needed.