Question

What is the best case time complexity of comb sort and bubble sort respectively?

(a) O(n^2) and O(n log n)

(b) O(n log n) and O(n)

(c) O(n) and O(n^2)

(d) O(n^2/2^a) (a=number of increment) and O(n^2)

The question was posed to me in class test.

My doubt is from Sorting in portion Sorting of Data Structures & Algorithms II

Answer 1

The correct option is (b) O(n log n) and O(n)

Explanation: Best case complexity for comb sort and bubble sort is O(n log n) and O(n) respectively. It occurs when the input array is already sorted.