I am trying to figure out the time complexity for a best case scenario shell sort. I know worst case is O(n^2) and I think best case should be O(n^2) as well because even thought its already sorted it still has to break the array down into gaps and check those subsets until the gap=1 but I am somewhat wary of my answer. A Google search returned no confirmation. Can anyone confirm this for me?

Thanks in advance

hi there.
maybe you're right but just in the case that you are only considering the comparisons, not the changes too.
its trivial, that if you want to sort an ordered vector, there wont be any changes, just comparisons.
cya

best case complexity is O(n)

R Sedgewick has some freely available material here : Analysis of Shellsort and ...