Question

The worst case running time of shell sort, using Shell’s increments is?

(a) O(N)

(b) O(N log N)

(c) O(log N)

(d) O(N^2)

I got this question by my school teacher while I was bunking the class.

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

Answer 1

Right option is (d) O(N^2)

The explanation is: The lower bound of a shell sort algorithm is mathematically found to be O(N^2).