What is the best-case cost of Shellsort for
an array whose size n is a power of 2 when using
divide-by-twos increments?
\Theta(n \log n)\Theta(n^2)\Theta(n)\Theta(2^n)\Theta(\log n)Think about whether the sorted list is a best-case input or not.
Sorted input is the best case.
How many increments are there for the divide-by-two increment series?
With divide-by-two increments, there are \log n increments.
\log n passes over an array of
length n must cost n \log n.