0

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

4
Contributors
3
Replies
7
Views
8 Years
Discussion Span
Last Post by radhak
0

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

1

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 ...

0

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.

Votes + Comments
Thanks for pointlessly repeating what was said OVER 2 YEARS AGO
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.