Question

What is the average case time complexity of gnome sort?

(a) O(n)

(b) O(n^2)

(c) O(n log n)

(d) O(log n)

This question was posed to me in an interview for internship.

This intriguing question comes from Sorting in section Sorting of Data Structures & Algorithms II

Answer 1

The correct choice is (b) O(n^2)

To explain: In gnome sort the loop has to take one step backwards every time any adjacent pair of elements is out of place which causes it to have time complexity of O(n^2) on an average.