 |  |  |  |  |  |  |  |
Quick question on Shell sort complexity
Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.
 |
•
•
Join Date: Apr 2008
Posts: 61
Reputation: 
Solved Threads: 1
Junior Poster in Training
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
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
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.
•
•
•
•
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.
"There is only one corner of the universe you can be certain of improving, and that's your own self.”
-- Aldous Huxley
-- Aldous Huxley
|
Other Threads in the Computer Science Forum
- Previous Thread: Really Don't Know What to Do!!!
- Next Thread: IT homework
| Thread Tools | Search this Thread |
You need to join our community in order to build your list of favorite forums. You can visit the forum index for a listing of all forums.
Related Forum Features
Latest Computer Science Posts
- Today's Posts
- Unanswered Threads
ai algorithm algorithms amazon assignment assignments automata battery bigbrother binary bittorrent bizarre bletchleypark blogging bomb business cern codebreaker compiler computer computers computerscience computertrackingsoftware connect conversion csc dataanalysis dataintepretation development dfa dissertation dissertationthesis dissertationtopic ebook employment energy floatingpoint foreclosure foreclosuresoftware fuel gadgets geeks givemetehcodez government graphics hardware history homeowners homeworkassignment homeworkhelp humor ibm idea ideas internet iphone ipod itcontracts jobs kindle laser laws linkbait lsmeans mainframes marketing mobileapplication msaccess nano netbeans networking news os p2p piracy piratebay principles programming rasterizer research sam-being-cute sas science security sex simulation software spying stephenfry study supercomputer supercomputing sweden technology textfield turing turingtest two'scompliment virus ww2
