What is the average case cost of Shellsort for a good increment series?

\Theta(n \sqrt{n})
  • \Theta(n^2)
  • \Theta(n)
  • \Theta(n \log n)
  • \Theta(2^n)
  • \Theta(\log n)

Shellsort does not have the same runtime as most typical sorts.

Shellsort is better than quadratic time sorts like Insertion Sort

Shellsort is slower than sorts like Quicksort or Mergesort.

Shellsort is not \Theta(n \log n) or \Theta(n^2)