‹ 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.