+1 vote
in Data Structures & Algorithms II by (110k points)
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

1 Answer

+1 vote
by (614k points)
selected by
Best answer
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).

Related questions

Welcome to TalkJarvis QnA, a question-answer community website for the people by the people. On TalkJarvis QnA you can ask your doubts, curiosity, questions and whatever going in your mind either related to studies or others. Experts and people from different fields will answer.