Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

I got some questions about complexity of shell sort and heap sort

I know worse case, average case of heap sort id O(n log n)

um...i'm just woundering whether the best case is also nlogn, and what if he complexity of heap sort for a sorted file..( i think those two stillO(nlogn), cos bulild the heap: O(n) + sort the heap still(log n) no matter the file is sorted or not)

but I'm not sure....

why the best case comlexity of shell sort is O(nlogn) not O(n^1.25)?

I know worse case, average case of heap sort id O(n log n)

um...i'm just woundering whether the best case is also nlogn, and what if he complexity of heap sort for a sorted file..( i think those two stillO(nlogn), cos bulild the heap: O(n) + sort the heap still(log n) no matter the file is sorted or not)

but I'm not sure....

why the best case comlexity of shell sort is O(nlogn) not O(n^1.25)?

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

thank you very much.

what about the best case comlexity of shell sort is O(nlogn) not O(n^1.25)?

i know it is based on the sequence, any sequence gives O(nlogn)?

and I'm just woundering the space complexity of quick sort , is that O(1)( in place), O(longN) or O(N)?

why we need the stack ?

So, you know that any sequence requires n lg n time to process with shell short. That means a monotonic array, a sorted array, a reverse sorted array or a completely random array will take that amount of time. If you believe that any sequence takes that amount of time then you are done showing that the best time is O(n lg n). Why do you believe that any sequence takes that long to sort? Explain it to me using the algorithm and I can help you with any speciific problems you have.

As to space complexity of quicksort and the use of a stack: Quicksort sorts the array in place (that is there is no additional array allocation required as there is in mergesort, for example). That is not the whole answer, though. Bubblesort uses O(1) additional space (we are talking about space BEYOND the original array) because you only need a couple of loop control variables and a temporary storage location for the swap; in particular, notice that bubblesort doesn't need recursion or an explicit stack, just some variables. Now think about what gets stored on quicksort's stack and why there needs to be a stack and not just a variable or two.

-bcl

the question about shell sort is....

cos I think the best case time complexity should be O(n^7/6) by Sedgewick,

but the answer is O(nlogn)

i'm just woundering why this is O(NlogN)

um...about the quick sort..

I have read through some pages on Sedgewick...

the subfiles in stored in the stack , when we need that, pop them off, and partioning and then push them back to the stack.so the average space complexity is o(logn) and the worst case is

O(N) when the file is sorted...Is that right?

Well, the worst case is simple: If we partition off one item at a time then there will be n levels pushed on the stack at its deepest. Thus the storage, worst case, is O(n). More interesting is the average case. How deep does the stack get?

Note: Shellsort is not one I tend to teach so my knowledge of analysis of it is limited. I was just reading http://homepages.cwi.nl/~paulv/papers/shellsort.pdf which works on lower bounds and goes beyond Knuth's work but I don't really have a good description of the proof (I can follow the paper but would not have gone there myself).

-bcl

anyway thanks a lot..

For quicksort: The key is the recursion. Assuming a perfect pivot (and a power of 2 size of the array), the amount of time it takes to sort a given size array, T(n), is:

T(n) = T(n/2) + T(n/2) + n

It took n operations to partition the array and it will take however long it takes to sort half of the array TWICE (each half) to finish the sort.

We also know that an array of size 1 is already sorted. This gives you a non-homogeneous recurrance equation. You solve the equation (by converting to a homogeneous equation) and you find that this "perfect pivot" sort has a closed form that is O(n lg n).

Alternatively, think about how many recursive calls will be needed for sorting a size N array. Assuming perfect partition, we need a depth of lg n recursive calls (n, n/2, n/4, n/8, n/16, ..., 2, 1; there are lg n numbers in this sequence and the sequence represents the size of the section of the array being sorted at each recursive call). If you think about ALL of the recursive calls, the calling diagram is a full binary tree (rooted at the call with size n which has two children, the call to sort the left half of the array (size n/2) and the call to sort the right half of the array (size n/2) and so on.

Does that function call diagram make sense? Total complexity is the total of work done in every node. Since the work is proportional to the size of the section of the array being sorted, each level in the full binary tree contributes O(n) work (each level processes the whole array, one piece per node). Thus the total work is proportional to the height of the full binary tree times n. But there are lg n levels in this binary tree so the total complexity of the sort is O(n lg n).

Hope this helps. Getting a feel for complexity is a challenge (learning how to find and solve recurrance equations can be very helpful if you plan on doing a lot of this).

-bcl

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Programming

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

For heapsort: if the file is reverse sorted (reversed from the order you want to end up with) then the array already contains an appropriate heap. Thus insertion into the heap is O(n). The extract operation (extract_min or extract_max, depending on order of heap) is stil going to promot the last element to the root of the heap and push it back down to where it belongs. Thus it is an O(lg n) operation performed for each extraction or O(n lg n) for all of them. O(n) + O(n lg n) = O(n lg n).

But wait, is this the very best case? What if the array is monotonic (contains only one value)? Then the heap is already in place as before (O(n) to realize this) _and_ promoting the farthest leaf to the root does not break the heap property so there is nothing to push down in the heap; extract becomes O(1) and is done n times: O(n) for all of the extraction operations: O(n) + O(n) = O(n). The best case is linear in array size. It requires a monotonic array to sort so it is unlikely to be of any real use but this is the best case.

I don't have my algorithm text handy so I can't perform the same analysis for shell sort but if I were to guess where the "best" performance would be I would try a monotonic array.

Hope this helps, -bcl