complexity of algo

Posted on 2003-10-31
Medium Priority
Last Modified: 2007-12-19
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)?

Question by:redsar
  • 4
  • 3
LVL 11

Expert Comment

ID: 9663452
What is the best case of a sort? This is typically not a relevant question because the best case typically can only happen for an already sorted input and, as n goes up, the probablilty of that input happening is smaller and smaller (arbitrarily close to 0).

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

Author Comment

ID: 9665084

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 ?
LVL 11

Expert Comment

ID: 9665650
This sounds a lot like homework. It is the policy of EE not to do homework. I can offer some guidance.

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.


Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.


Author Comment

ID: 9666242
i guess it is a misunderstanding because of my english.

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?
LVL 11

Expert Comment

ID: 9666349
Do you have to push copies of portions of the array on the stack for quicksort? Or can you get by with just the endpoints of a range in the array? If you push the endpoints of a range you need a constant amount of space each time you push on the array. Thus the total amount of space used is proportional to the maximum depth of the stack. What is that maximum depth in the best case? What is it in the worst case? The average case?

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


Author Comment

ID: 9666482
Thanks a lot....i think the main problem is I don't know how to calculate the space complexity and time complexity....of course, some questions are very easy, like insertion sort and seletion sort, but for the difficult analysis like quick sort and merge sort...i don't know how to deal with..
anyway thanks a lot..
LVL 11

Accepted Solution

bcladd earned 160 total points
ID: 9666615
The first step to calculating complexity is figuring out what is executed/allocated most often. Then count how many times that happens.

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


Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In this post we will learn different types of Android Layout and some basics of an Android App.
Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
Simple Linear Regression
Screencast - Getting to Know the Pipeline

807 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question