Quick question on Shell sort complexity

[chunalt787]

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

[nibauAntunes]

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

[xkey]

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

best case complexity is O(n)

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

[radhak]

shell sort
Best case: O(n). It occurs when the data is in sorted order. ... Worst case: O(n^2) if the numbers were sorted in reverse order.