Question

If Hibbard increments (h1= 1, h2= 3, h3= 7, …, hk = 2^k–1) are used in a Shell sort implementation, then the best case time complexity will be ________

(a) O(nlogn)

(b) O(n)

(c) O(n^2)

(d) O(logn)

The question was asked in a national level competition.

This interesting question is from Shell sort topic in portion Sorting of Data Structures & Algorithms II

Answer 1

The correct choice is (a) O(nlogn)

Explanation: The best case occurs when the array is already sorted. In best case the number of comparison for each of the increments-based insertion sorts is equal to length of array.

Here 2k –1 < n, where n is the number of records. So k < log(n+1), thus the sorting time in best case is less the n * log(n+1). Therefore best case time complexity is O(nlogn).