Question 12 Which of the following is the worst-case complexity of Bubble sort?
Palo Alto Networks technical mcq question, verified with a worked answer. Free to practise - no sign-up.
Which of the following is the worst-case complexity of Bubble sort?
Select any one of the following options
Show answer & explanation
Answer: A. A) O(n2)
Bubble sort makes n-1 passes, comparing adjacent elements. In the worst case (reverse sorted array), it makes n(n-1)/2 comparisons and swaps, giving O(n^2).
Step-by-step Derivation:
Step 1: On pass 1, Bubble sort performs n-1 comparisons. On pass 2, it performs n-2 comparisons, down to 1 comparison.
Step 2: Total comparisons = (n-1) + (n-2) + ... + 1 = n(n-1)/2.
Step 3: Therefore, the worst-case time complexity is O(n^2).