Ad:

Computer Science Discussion Thread
Unsolved
Views: 3239

Sep 19th, 2008

Quick question on Shell sort complexity

Expand Post »

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

chunalt787

Reputation Points: 39

Solved Threads: 1

Junior Poster in Training

Offline

84 posts
since Apr 2008

Permalink

Mar 22nd, 2009

Re: Quick question on Shell sort complexity

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

Last edited by nibauAntunes; Mar 22nd, 2009 at 9:44 pm.

nibauAntunes

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

1 posts
since Mar 2009

Permalink

Mar 26th, 2009

Re: Quick question on Shell sort complexity

Click to Expand / Collapse Quote originally posted by 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

best case complexity is O(n)

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

Last edited by xkey; Mar 26th, 2009 at 12:57 am.

xkey

Reputation Points: 15

Solved Threads: 0

Newbie Poster

Offline

13 posts
since Mar 2009

Permalink

Jul 27th, 2011

shell sort

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.

radhak

Reputation Points: 6

Solved Threads: 0

Newbie Poster

Offline

1 posts
since Jul 2011

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in Computer Science Forum Timeline: Dijkstra's Algorithm(Priority- First Search)

Next Thread in Computer Science Forum Timeline: What's the difference between being a computer programmer and a software engineer?

DaniWeb Message

Cancel Changes

User Name
Password