Question

What is the worst case time complexity of comb sort?

(a) O(n^2)

(b) O(n log n)

(c) O(n)

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

I had been asked this question in homework.

This is a very interesting question from Sorting in chapter Sorting of Data Structures & Algorithms II

Answer 1

The correct option is (a) O(n^2)

The best I can explain: Worst case complexity is observed when the input array is reverse sorted. This is same as the worst case complexity of bubble sort.